I just bought Hitman Absolution for PS3 on the PS Store. When I tried to download it said: No space. When I checked it turned out that I indeed had to less space. I decided to do a full formatting on my PS3 as it was to full and I didn't really care for the data what was located on my PS3. When I was done I still had the error "No space". I believe that is kinda weird, because I now got 31GB!! free space for a game the size of 17GB.
Why won't it download?
You need at least double the size of the game download available on your hard drive to download and install the game. So, you would need 34 GB of free space in order to download and install a 17GB game. Then after installing, you'll have 17GB free.