Ah, well you are finding out, like every other widescreen owner in the land, that there is simply no satisfactory way to watch 4:3 broadcasts on a 16:9 screen!
You have a few choices with most:
1) an allegedly clever mode, as you are using, whereby it stretches the picture more at the edges than at the centre.
2) Cropping the top and bottom of the picture in order to fill the screen with the correct aspect ratio, but losing some picture
3) stretching the 4:3 image in a linear fashion to fill the screen with fat people (unless they are lying down, in which case they become tall and thin)
4) a mode that does a little of 2 and a little of 3 (called "Smart" on my TV)
However, the best way to watch them is with borders down the sides. It sucks, but I'm sure people with colour TVs got miffed with being forced to watch black-and-white repeats.
Thing is, 99% of British programming is shot in widescreen and has been for years. I've been watching widescreen digital TV broadcasts since the days of onDigital, back in 1999 or 2000. Even "Neighbours" was in widescreen then (being a student I had much time to watch it!)
The only things I find aren't are on the lesser channels or are "international" programmes that are dubbed into English (e.g. all those shows about American cops, many have English narration). Whilst it has taken them a while to catch on to widescreen, many American programmes are also now made in widescreen... some even in high-definition which will come in handy from 2006!