check the software version in your car and the iphone IOS version, maybe your issue is down to your replacement phone running on example ios5 version, and your car software version is way behind, a number of treads exist like this one
http://f10.5post.com/forums/showthre...&highlight=ios, mind you if your car is a 2012 the gap should not be an issue.