I have a Creative 40Gb as well. Here's my question: do you really listen to ALL of your albums all the time?
I don't. I could probably get away with 5 or 6 albums plus the podcasts, and keep the albums on my backup HD.
My advice to you is to buy a new Shuffle and forgo the Nano. It'll probably last you two or three years with daily wear and you'll come to realize that Dio's Holy Diver is NOT a must have at every moment.
http://www.apple.com/ipodshuffle/