iMac external projector limits screen resolution to 800x600
It sounds like OS X isn't properly detecting the resolutions your projector can support.

The best workaround would probably be SwitchResX. It's a shareware app (from what I can tell, no functionality restrictions) that allows you to set custom resolutions (and other display options). Set up one that you've confirmed your projector can support and give it a try.