Hopefully you also have the current firmware installed. If you do follow below:
Does it acquire satellites faster if the SD card is out of the unit? Should be less than one minute to acquire without it.
If it is faster without the card, then you got some buggered up files on the cards: too many songs (+1000 is bad), screwed up MP3 tags or some that aren't tagged correctly, corrupted *.gpx imported files, or just a bunch of fragmented/buggered stuff that occurs at times, etc. on the card. Less likely would be a buggered *.img map file on the Zumo itself. If so, backup all files on the Zumo for safe keeping and reinstall the larger map files.
You can try and installing MP3 files in multiple folders. If that works great. However, chances are you have a corrupted MP3 that the Zumo skips during the initialization in multiple folders and may never play in random mode.
Mine occasionally "burps" a file on the SD card for whatever reason (skips, locks-up, slow loads, SD card read/writing errors, etc.). I have to check it once a month or so against a master MP3 list off an external hard-drive. I also have around 600 MP3's in ONE folder and boot time is about 55-64 seconds. A lot of it may be the ID tagging methods you use on the songs too (I strip off all track numbering info from each song as too many formats on numbering exists (e.g. 0-1, 1, 2-15, 0, 1/12, 03, etc.). I name Genre as "All Music" vs. Country, Jazz, Pop, whatever" and keep the album art to less than 300x300 pixels and <22 Kb in size. Too much stuff clogs it up, imo. It isn't the best nor smartest MP3 player around.