I have the same phone and it works just fine. Try deleting the phone and readding it. Also check under options and make sure you have the contacts box checked off.
My only question is when using Pandora, does it list the song names on the display or do you get something like VoiceNotes12345 as the displayed song name?
Also does the messages feature only work with the iPhone?
2011 M3 Sedan - Jerez Black, DCT, Comp, Navi, etc...