Sounds like it may have been a problem of having crossed maps between units. Each full map set is keyed to the serial number of the device for which the specific set was produced. So if backups got fouled up (Home is dreadful about this sort of thing), and the wrong map wound up on the wrong unit, you would definitely get "You Can't Use This Map..." The firmware / map combination isn't important to that. You can run very old maps on new firmware, and you can run new maps on rather old firmware as well. So I suspect it was a problem of getting one or more map files from one unit onto the other one by mistake. Like I say, easy to do when using Home for anything related to multiple units, or even during manual restorations, if care isn't used.
It is for that reason that we recommend always using the PC's own file system to back up each device into its own folder for future reference. Can't hurt to name the folder using the last couple of digits of the serial number just to keep them 100% straight, especially when you have more than one of the same model of these older units like you and some of the rest of us have had at one time or another.
The new gear is a whole lot simpler since everything needed for a restore can be had from the TomTom server, including any maps -- which are the bugaboo when it comes to backups, device formatting, etc. It's always CRITICAL that there be a good PC backup of the last working map for any older unit you have.