Remove old autocomplete entries in Messages (iOS 6)

I have a friend who changed her phone number recently. When I start to send her a text/iMessage, her old number still shows up in the autocomplete list when I start typing her name, even though I've removed it from her contact in the Contacts app. How can I get rid of the old entry?

Note this is in the iPhone messages app (the behavior does not duplicate on the iPad messages app, nor in Mail...just in Messages on the iPhone).

My iPhone is a 4S running iOS 6.0.2.