iOS 4 has NOT been released yet.
As soon as iOs 4 is OFFICIALLY released apps like Pandora will update their app to enable it to play in the background. Jobs showed off the version of Pandora that will be released along with iOS 4.
People really need to wait until the 21st when iOS 4 is released. Keep in mind the only people that are supposed to have iOS 4 are developers not the average user.
ANy app that is updated with 4.0 compability is backwards campatiable, so there is no reason that they have to wait. With regards to Pandora it is one the big ones and I am sure they want to make a splash with it, just my thought. I think there will be a lot rolling out shortly.