Just out of curiousity, are you using a memory card in the microSD/microSDHC slot? If you are, try removing it and see if it works OK. I just replaced my old Fuze and it takes 15 minutes to start up with the new one, even after doing a manual firmware update, but as someone mentioned in another thread, they removed the external memory card and it worked fine. I’ve tried the same thing and get the same results. If I remove the memory card and boot up, the ‘refreshing media’ message only lasts a minute or so.
(see the thread http://forums.sandisk.com/t5/Fuze/Sansa-Fuze-Freeze-s-at-Welcome-Screen-HELP/td-p/85384 for more)