We own a 2011 Hyundai Tuscon and I had the same problems. My wife's Blackberry synced up fine (after I made some configuration changes on the BB). I tried everything to get the Tuscon to take my phone book, but to no avail. I can use the phone with the car's BT for phone calls. I just have to "decline" the request to transfer data from the car on the phone (an EVO 4G with 2.2). I have to do this every time the phone and car connect. It's a pain.
You probably have done this already, but search Google for "Android Hyundai Bluetooth", etc. I did this when we bought the car, and noticed the issue with no solution, back then.
One last thing... Grab
Bluetooth File Transfer from the Market. I did get it to transfer some of my phone book but I ran out of time to really test and tinker with it. This may be a solution.