It's not the disk space so much as the number of tunes on the player. If you encode all your tunes at a high bitrate, then 56 gigs will hold fewer tunes than if you'd encoded them at lower bit rates.

The number of tunes that gives the problem also seems to depend upon how much tag information is filled out, such as data residing in comment tags (if I recall correctly). So the exact number of tunes isn't the same for any two players, either. But I've heard reports of some players having database-size-trouble when the number of tunes gets into the teens of thousands.