If you have Verizon like me, you have to re-sync to the Cloud - b/c your Phone's Contacts are pulling in from 2 possible locations (Google and Verizon Cloud).
I re-synced to the Cloud so it saw a deletion of the original phone number, and voila, your Contact no longer pulls in your old # from...