I've had the same issue just noticed it starting today. I had apparently been sent some messages yesterday but not received any. I've just rooted the phone this week too, so I was worried I've mucked it up or something... but suddenly a flurry of texts came through from today (not the ones from yesterday though).
I'm with 3 and has 2.1-update 1 (thats how I got it, hasn't been updated since I've had it)
The texts came through as I was updating some apps, don't know if that had anything to do with it. And I did have the 'low on space' message, removed loads of stuff but didn't do anything until I was updating the apps.
just to pool some more info