Whether you have a CRT or an LCD, you might have to use the geometry buttons to adjust display width and height to fill the whole screen (on one older LCD I have to do this). If you don't have an auto-adjust button, you may need to look in the manual to figure out just how to do this - I've always had trouble with navigating these kinds of menus. If you don't have the manual handy, you should be able to find one on the manufacturer's website.
Then again, as nightflier and uelsk8s said, it could be a driver problem. I don't know much about that.
Hope this helps.