Have you considered using a lightweight window manager on top of
X as opposed to the full Gnome desktop environment that comes default? This can use a lot less memory.
Most of the *Box variants are very lightweight. BlackBox, OpenBox and FluxBox come to mind. XFCE is also fairly lightweight.
The desktop environment that comes with Ubuntu by default is called Gnome, it isn't exactly the best for memory use. Using just a lightweight window manager on top of
X (www.X.org) doesn't have to look bad either, here's a picture of Openbox:
Gnome has a lot of features that you may not need and a lot of eye candy, especially with compiz. If you don't need this I think you'd like a small window manager.
This guide will get you up and running with a low memory environment on Ubuntu.