When (and only when) you are at country level from the locations tab, you should notice the MORE button at the top left of the navigation bar.
This heralds a great new feature that we added in version 2.5 for extending the location database from the (new for version 3) 200,000 entries stored on your phone, to the millions (8 million as we write this) of entries that geonames.org have in their database.
To use this great online database, simply enter your search into the box and then click the SEARCH button on the keyboard that will be showing.
The more letters you enter of your search, the faster the results will be returned, but you can just search for a few letters if you want to and the results will be those places starting with those letters.
geonames.org is a fantastic online resource, but we can’t guarantee its availability so if you do experience connection problems, please try again later on when their servers may have more capacity.