I just went throught a similar situation...
1st...did you uncheck 'Overscan' in System Preferences? (I'm sitting at work so I don't have access to the Mini to be sure where 'Overscan' is located)
2nd...your TV should have an overscan option in its menu someplace, my Sony does.
When I originally hooked up my Mini to our TV, regardless of resolution, I was getting overscan (top navigation bar was totally gone, and half of the dock was hidden). Un-checking 'Overscan' in System Preferences produced a smaller image with black borders all around and selecting +1 overscan in the TV menu produced a centered picture filling the entire screen.