I have had the exact same problems with the 'alert your phone is running low on free storage space. Delete old or unused items to create more space.' and 'INFO SMS storage is full'. I have had these errors on on three different i300's.
I have called Samsung and O2 and both have been useless, they don't even know about the problem. Or atleast that is what they are saying. In the end I sent it all back and have given up on this phone.
Samsung wanted me to send the phone back to them for repair but I didnt bother doing this. Call me cynical but all they would do is perform a hard reset and then say its working, send it back to me and then charge me for sending a device which is 'not faulty'. Well who knows maybe they would have done something but I aint sending my brand new phone for a repair!
So three Samsung I300's and same errors on all, how mint!
Shame really as I thought it was fantastic otherwise. It sounds like a OS problem to me, I cant see how filling the HD could cause this as I had 600Mb free everytime these errors came about. Even if it was the HD its stupid not being able to fill your 3GB HD with music. I also never installed any apps, so the only phone memory being used was for contacts, couple of sms, settings.
My advise to everyone is to steer clear of this phone unless Samsung release a fix. Unless you fancy leaving your phone switched on permanently, as the error only seems to appear intermittantly when you switch it off and then turn it back on again.
I mean imagine the thing crashing while your out and about to meet whoever and then you turn it back on, get the error, have to do a hard reset, and then you find out you have lost all your contacts.
I find it hard to believe that a company like Samsung could release something as major as this but not test it thoroughly enough to find this error. Or maybe they did and released it anyway so they could say they have the first HD smartphone on the market!