Nathan,
I did some playing around, and you are correct. My G4 is also only letting me go to 1024. It went higher when I had a display connected, but not now.
I believe the problem is that OS X only allows you to set a resolution that it thinks is compatible with the connected display. If you're like me right now, you're running your remote machine headless, with no display. I guess in this case, OS X defaults to allowing only 800x600 or 1024x768.
Other than using JollysfastVNC, and dragging the VNC window to a larger size (which makes the remote screen look fuzzy since it's scaling 1024x768 to a higher resolution - which I am OK with), I don't think there is any solution working just with the OS X display and VNC settings. However, the application SwitchRESX will allow you to override the OS X limitations and set any resolution on your server, so perhaps this will solve the problem. I have used it in the past but am not using it on my current system. It's available at:
http://www.madrau.com/
Steve