Personal Message space is limited... however, it shouldent do this...
From what I recall, it should just start deleting old messages.
Have you tried logging in and out again, or is it working now?
The Administrator can change the size of the PM box, however, not for individual users, though, Nathan may be able to "prune" a users box, it is up to them.