A battery pull is usually good advise, but this is one of those time when it does not accomplish the goal of freeing up the scratch pad memory used by an application download.
I had a similar failure with one of the BlackBerry Messenger upgrades. A big chunk of memory was missing.
After repeating the download and install, the missing memory re-appeared.
Once you have it cleared, you can then remove the application totaly.
You can schedule the memory to auto clean. Menu/ Options/Security Options/Advanced Security Options/Memory Cleaning. Quite a selection of choices. You can also place an icon on your home screen for quick access.
Posted from my CrackBerry at wapforums.crackberry.com