This never happened with my 10 GB player, so I've kind of chalked it up to having 2 disks or something.

Nope, it's not supposed to happen regardless of the number of disks. This is puzzling. If you downgrade to 1.03, does the problem go away?

I have 26 GB of MP3s (4,400) so only one disk should be full.

That's not how it works. Please see this FAQ entry.