*** The solution proposed on this topic is already obsolete, due to the improvements made over the last two years! There's still some stuff to work on in order to have your UI working flawlessly on different devices, though...
I'm working on a skeleton project so I don't have to start things from scratch everytime I'm working on a project.
Today I came up with a nice solution for multiple resolutions, avoiding those annoying black bars no matter how stretched your screen is.
It is also ready to be used no matter the orientation: You just have to change the layout sizes to a portrait orientation (say, 640x960).
Hope it helps! I still have a lot of things to add on the skeleton (level selector, sound options, facebook integration), but this is was a nice start, so I wanted to share it with you.