Unable to Clear Search Maps in Google Maps

[tourboy]

On my Samsung Nexus, I am running version 4.1.1. When I go into Google Maps and at the top click on Search Maps, it has a history of all the places I have searched. How do I clear this list?

I have tried going Settings, Apps, Google Maps and Clear Data. Then went back to Google Maps and its still there.