In Exchange 2007/2010 after you change mailbox limits either globally or for an individual, it will take around an hour or two before these changes are recognised.
This is to do with Active directory and the fact that a lot of information relating to it is cached and is only refreshed every hour or so.
If you want the changes to take effect sooner, the easiest way to do this is to simply restart the Exchange Information Store service.