What's the difference (except packages) between ubuntu-server and ubuntu-desktop on aws when they use the same linux kernel image (http://packages.ubuntu.com/lucid/linux-image-2.6.32-313-ec2) ??
The main difference between one and the other is the packages loaded, as you've pointed out, so I won't get into that one, other than to say it's a remarkably bare install using ubuntu server. This is surprising only because of how much is stuffed into ubuntu-desktop.
The other differences of note, to me anyway, is the install - there are many more options on how to configure your system out-of-the-box such that once the install is done, you already have much of what you want (and don't have much, or all of what you don't).
Finally, there's the kernel. The ubuntu-server kernel is server optimized. Some details of it at the link below, but google will likely find you even more specific differences:
Now, if the kernel is the same in both (likely has VM doo-dads in it), then there is really not much difference than what the installer brings to the table, but if even the installer doesn't come into play, then there isn't much difference at all other than the packages you get out of the gate, as you mention.
Besides the kernel and the packages you get by default (for example ubuntu-server doesn't by default install X/gnome/kde/unity for you, but you get with desktop) I know of no other differences. If this is on AWS, chances are you want -server.
For further info on this you can see at this other question: Can Ubuntu Desktop "become" Ubuntu Server?