I discovered something similar with my car's MP3 player - it would only handle a maximum of 99 songs per folder.
admittedly 15 songs is a pretty dismal limit, but try only putting 15 songs in one folder and 15 into another, put the player in shuffle mode and see if it reads all songs that way.