Well many here would advise ditching Express and using GarminMapUpdater but if you want to persevere with Express ensure you have the latest version http://download.garmin.com/omt/express/B/GarminExpressInstaller.exe
You may also need to clear out the temp directory as explained in this thread https://forums.garmin.com/showthread.php?42340-Neither-Garmin-Express-Nor-Map-Updater-Working-for-Me&p=192112#post15 by KGANSHIRT
Can you go to Tools>Settings>myMaps and say what is shown there?
Also how much space is showing as used and spare when you check your nuvi's properties on your PC?
Check too the garmindevice.xml file in the Garmin folder, what size is it?