I had the same problem after upgrading to iOS 5.1. In addition to the issues you mentioned, the Music app got really slow after start up, taking up to 10 seconds to respond to my taps and touch gestures.
As I couldn’t find a simple solution to the problem, I ended up restoring my iPhone to factory defaults (this is basically a clean iOS 5.1 install) and started over. This fixed my problem.
Update: Seems like there is a workaround:
If you’re trying to install a handful of iOS apps and your entire home
screen is filled with app icons labeled “Waiting…” without any of the
progress bars moving, downloading, or installing, you can fix this
fairly easily with the two methods below. Try the first method before
going nuclear with a reboot though:
Tap a single app icon so that it says “Paused” and then tap that app
icon again to see if it resumes downloading If pausing and resuming
didn’t work: Reboot the iPad, iPhone, or iPod touch You may notice a
related issue where apps from the App Store will say they’re
“Installing” though they aren’t appearing on the iOS home screen yet,
that is also resolved with a reboot.
It’s not totally clear what causes this, though it seems that a lot of
people are encountering the problem right now when moving from an old
iPad to a new one. It could be that Apple’s servers are just
overloaded with downloads from the App Store, or it could be a bug.