I'm confused on what the problem is, and the suggestions are also pretty varied, but I've done a pretty good deal of research on this stuff. If you have a 16:9 widescreen TV, then a 16:9 widescreen DVD will fill up the entire screen. When I first got the widescreen TV and new DVD player, I had to change the setting on the DVD player from 4:3 to 16:9.
HOWEVER, the word widescreen can be misleading, because there are actually two sizes:
16:9 (which is referred to as either 1.85:1 or 1.78:1; the difference is not noticeable), which is as big as widescreen TVs get as well as...
64:27 (always referred to as 2.35:1 or 2.40:1; again the difference is negligible), which is the size many movies use (though some still use 16:9).
Because the latter aspect is bigger than a 16:9 TV can fully show, there will be horizontal letterboxing on the top and bottom of a 16:9 widescreen TV. The terms I've bolded are the ones that you can find on the back of a DVD box, which indicate the aspect the DVD uses.
What I'm surprised by is that fact that the original poster said that they tried to change the size, but it didn't work. I know that with my setup, I have one set of settings that change the aspect on the program I'm watching on my cable remote, and one that changes the aspect of the movie I'm watching, which is on my TV remote. Maybe that'll help.