That would account for almost 20GB though?

I'm assuming it compressed your data a little bit. That's the only thing I can think of. I suppose you might as well try and put in the new HDD and try and restore from your backup. You will never know until you try. If you backed it up twice and it was the same size both times, then that's probably the size its gonna be. 

I've got my new 500GB HDD set up now, and it works fine, I just had to redownload my games, some of the game utility data. I'll install the rest when I want to play those games. Even if you end up having to redownload everything, at least you got the new hard drive installed. It's not too big of a deal as long as you have your save data safe.

True, not much I can do with 20GB left on the HDD