I can't help solve the problem (it doesn't make any sense to me) but I can tell you that 115 playlists is nowhere near too many. I can't remember anyone having this problem before (spontaneously disappearing playlists) but the symptoms you describe make sense beyond the fact that the playlists are disappearing in the first place.

Have you used jEmplode? Does it take a long time for the empeg to boot up?