How do I recover purchased music on my iPhone 4? I replaced my iPhone 4 today and used iTunes to restore all of my settings, contacts, calendars and apps. Everything but my music was restored- including my purchased items. I have tried the iTunes Store on iTunes and on my iPhone and I feel like I'm missing something- is there another step that I should be taking when restoring to retrieve my music?
It appears there are multiple ways. The first, is outlined by Apple here.

Automatic Downloads and downloading previous purchases are not compatible with iPhone 4 (CDMA Model). Automatic Downloads and downloading past purchased music and TV Shows is supported only in the US and is not compatible with iPhone 4 (CDMA Model). Previous purchases may be unavailable if they are no longer on the iTunes Store. Downloading past purchased TV Shows requires iTunes 10.4 or later.

It details the following methods:


Open the iTunes Store on your device.
Make sure you are signed in with the same account used for the
    original purchase.
Tap Purchased from the bottom navigation bar.





From the Purchased tab, tap the artist name for the content you
    intend to download again.
Once you've located the music you are looking for, tap the download
    button.




Note: To download all songs from a purchased album, tap on the Album's toggle button to switch to Album view.

Once you redownload the music to your phone, they will transfer to your iTunes library when you sync the device.

And an alternate method using the new iCloud service can be found here (it's of note that when I tested this method, I could redownload books and apps but not music; your experience may, however, differ).