Now I'm unsure if you're talking about the background or the subpicture overlay (or both).
Maybe you could post it for us to look at.
I didn't realize I was on the Encore forum so take my comments as DVD spec related.
Most DVD Authoring programs, when importing still menus automatically encode the MPEG2 still at 8Mbps, so it wouldn't necessarily get any better if you encoded it on it's own (as a video clip). You may try to import using a TIFF instead of a PSD.
You need to make sure you're looking at, and providing, what is required (and limited) for DVD. In it's most basic form - a TIFF (or TGA), RGB, 16bit, flattened, 720*480 (for NTSC), 72 dpi, square pixel (you should compose with pixel aspect correction)... avoid serif fonts (or any small fonts), respect title safe and NTSC color gamut and remember that all DVD playback is inherently interlaced. Thin lines can "buzz". Pay attention to the overall complexity of the menu. Since the encode is MPEG2 there are only so many bits to go around. Gradients and small patterns can lead to compression artifacts where you don't want them.
Remember, DVD's were meant for SD CRT TV's with analog component video. Computer playback and plasma/LCD monitors came later. Make sure you have a good reference monitor and an assortment of players, at least something you trust. Then you can suss out the results coming from players that upscale (or don't), flat screens with different refresh rates and computer playback which may be software de-interlaced... all of which can look a little different.
Roger Hendrick
The Airship Factory
http://www.airshipfactory.com
HD Video Production - Blu-ray Authoring