Weird.

I had this issue for months. I fixed it by going into the TV settings and changing the aspect ratio (the thing that has options like cinema, game, panoramic, etc.) to 'full' or something like that. My TV is a cheap department store model, so it's nothing special. And my XMB fit before I changed the setting. There's just more of it now.

Given the solution, I can't see how this is a client-side problem.