Something similar has just happen to me.
I just download 3 new songs over 3G onto the phone(new David McCormack ex Custard FWIW).
When I went to the iPod on the phone to listen to them, all the other music was gone. Only the three newly downloaded tracks are there. Although the disc space it still being used.