This is a common problem with the update to iOS5. For some reason, it is not making a backup of the app data before the upgrade. We are not sure what is causing this but it may be caused by syncing the device with more than one PC, or by using more than one itunes account to buy apps.
Don't worry. Nothing you have purchased has been lost. If you sign into your account (flip side > Settings > Map licenses > Sign in) it will automatically recover all your licenses. It sounds like you have already done that.
You do still have to download the maps, and there are various ways of doing this, depending on the type of map.
If you have the maps on your PC, you can copy them to the iOS app using iTunes file sharing. This used to be a feature of the Paid app but is now included in the free app.
If you have a DMS Selections map (such as the OS 1:25k Explorer), where you have to activate areas by the sqkm, there is an easy solution. First open the map from the Digital Map Shop, then tap the Maps folder button on the toolbar and tap the blue detail button to the right of the map. Tap "Bulk Download", and "Download All". This will re-download all the areas you have previously activated.
For other kinds of maps, where the license allows you to download any part of the map, just use any of the bulk download methods to re-download the map. Memory-Map does not keep any record of the areas you have downloaded. I suggest creating a route, either along a path you intend to travel or enclosing an area of map you need. Then tap one of the waypoints, Edit Route and Download Map.