The problem isn’t with Encore, its with the monitors. All TV monitors have what’s called “overscan”, which means that the image on the screen is at least 10% enlarged. On older sets it can be as much as 20%.
To be sure your menu displays properly, design it so that all buttons and text fit within what post production people call “tv safe”, a rectangle centered in your 720×480 frame that measures no larger than 648×432 (10% smaller than the whole frame).
Also, I don’t know if this could be a factor, but only professional NTSC is 720×486. Consumer DV is 720×480.