Note: most of this is speculation, as I haven't personally written or dissected an iPhone application.
There's the possibility that any application could be accessing information available on the phone and sending it back to their server: the free game Aurora Feint was removed temporarily from the store, not specifically for reading your contacts list and sending it back to their server (which it was using so you could see if any of your contacts were playing the game), but for storing a copy of the contacts list locally on the iPhone and for not transmitting it securely to the server. Did the application need to ask for permission before accessing the user's contact list?
Perhaps Apple's process of approving iPhone applications for the App Store involves finding out which of the OS frameworks/data stores the application needs to access and granting it the appropriate permissions. Surely applications aren't just allowed to access the location, contacts, calendar, email, etc without asking? As Chris Josephes pointed out, "Twitteriffic needs permission to know where I am; but MyStreets doesn’t need permission to read and sort all of the contacts on my phone. And with VoiceRecord, I was never prompted for permission for the application to listen to my microphone".
There's also the question of what personal data is given to the application seller by Apple when you buy it from the App Store. Presumably they get your email address so they can send notification of updates, etc, but do they get your full name and address? It's treated as a proper transaction regardless of whether the application is free or not. Could providers of free applications be selling email addresses to the makers of other, paid, applications for marketing?