Why does my Android OS state that there's, "Not enough free space to install the program", when there's plenty of free space? My hard drive on my smartphone has 100 MB free, and the app I'm trying to install is 2 MB.

I just recently deleted apps totalling to about 88.3 MB, and the computed size has already been adjusted, and is displayed on the screen.

However, I have to wait 10 or 15 minutes to install it.

It's as if the updated, computed space is not registered in some way to the operating system immediately.

It's Android 2.3.4 Gingerbread, no root, no unlocked; factory pre-set all the way(not for long though).

So, basically, is that the problem? Why do I have to wait a while after uninstalling apps, and re-computing space availability to above par to install a new, extremely small app, to actually work?

Is this all the OS's fault, or is something else at play here(e.g., hard drive or circuit-level operations reigning outside the control of just the OS software)?

Because if the re-computed size is what it's going to be, at least let the end-user know that rather than give the impression that you have the available space, but it won't install anything.
This can be caused by having any partition full, so you can try clearing your cache and other partitions that might be full. I'm guessing it's the cache since it clears out by itself.