Why is there such a difference in the amount of internal memory?
Your confusion is most likely caused by the way the Playstore handles installs/updates. They are first downloaded and stored in internal storage (not on sdcard, but /data/local), then the app is to be installed on the same partition (/data/data/app.package.name) -- only after that the download can be deleted.

In your case, this would mean a 12M download, which then needs to be unpacked (at least another 12M, or rather more) -- which could sum up to 30M or more. A safety margin needs to be kept to keep the device from crashing -- so you get the "insufficient storage" error.

See also: Package Install via Market sometimes fails and gives seemingly random error message