I have the exact same problem. I've restored, updated, plugged in the earbuds over and over as I was told. The earbud trick seemed to work after plugging and unplugging over and over during a call.
The speaker would only work for about 20 seconds after that though. After several calls to apple, time to send in. My loaner arrived today and mine is being sent out in the morning.
I posted about my loaner, please wipe your phone if you send it in. Here is my post.
http://www.everythingiphone.com/foru...ise-14360.html