In Karmic Koala, Ubuntu 9.10, the packages are still there but they've changed names! So if you want to use screen with Ubuntu Karmic or later, install packages byobu and byobu-extras, and uninstall screen-profiles and screen-profiles-extras (they were broken on my system after upgrade anyway) and you should find everything works as expected. To run screen with the new features, you should run "byobu" instead - although screen commands seem to work to detach and reattach the screens that result, weirdly.
I'm mostly posting about it because I have been very frustrated and there's no way I could have guessed, or probably ever will remember, what these packages are called. Apparently a byobu is a japanese room screen ... you learn something new every day!