Interesting. I have the exact opposite issue. My new iPad downloading fine. My iPhone 4s won't download apps or music. Thoughts? I'm in norther, nj if that means anything.
This happened to me..all apps were stuck waiting, I couldn't download or update. I could only get new apps on by synching from the computer. Tried hard reset, logging in and out of app store. The only thing that worked for me was a restore.