apt-get will only work if the repositories you've got have the package listed. You may have to add the universe (? been a while since I used ubuntu) repository if you haven't already.

The other option is to start at the command line and work from there, personally, I find it easier to get things done that way as I can see what errors are generated.

Has anyone tried Fiesty Fawn yet? Any better than Edgy? I use OpenSUSE myself and, while I'm happy with it, I'm still interested in what's happening on the (K)Ubuntu front.