After installing VBox Tools your Ubuntu screen should be resizing automatically as you resize window size. Unfortunately despite enabling option: Machine->Auto resize guest display, the display stays as it is.
- resize the window size as you wish, then go to guest system and try: System->Preferences->Monitors (under gnome). There should be a resolution that fits your CURRENT window size (the biggest one)
The size is also set correctly after system restart.
There is no patch for this bug yet (VBox: 4.0.4, Ubuntu: 10.10 Server)