Resolution and Aspect Ratio - not the same thing
"Freeview channels displayed correctly, but the signal from our Sky+ box was initially displayed at its standard 576p resolution, which left it with big black borders on either side of the image."
For a start, if it's a standard Sky+ (not HD) box, it'll be 576i not 576p.
Secondly, 576 is the number of vertical, not horizontal pixels, so that wouldn't affect black bars on the sides of the image anyway.
Thirdly, the SD resolution doesn't tell you the aspect ratio in itself. An SD PAL signal is usually encoded as 720 x 576 but the signal contains an Active Format Descriptor (AFD) which tells the TV how to present the video on screen. So basically a 16:9 widescreen programme in SD PAL may have the same 720 pixel horizontal resolution as a 4:3 programme - it's just that the pixels are effectively wider in the widescreen version.
So marksi is right. If the TV puts black bars either side of the image, it's doing it so that you can enjoy your favourite TV characters without fat heads.