I have never had that not enough space problem. However, I noticed that, in their directions for upgrading firmware, it states that you should have over 50mb of free memory to safely update your firmware. I suppose that could apply here too. It is possible though that scanning and building a database might require even more space on the drive. I would start though by making sure that you have at least 50mb free minimum and work from there.
Yup I had 16mb free at that time. I have since figured out how to get my SD card files to show on my player so now the bulk of my albums are on them. Everything is working as it should and I'm super happy! Thanks for all the help everyone.