Well this was unacceptable and the taketwo's advice was of little help. So I decided to think what could I do to try to fix this. Well, what makes my PS3 'different' from the norm:
- 160GB HDD
- USB connected 60GB HDD
- Memory stick inserted
- PS Eye Camera connected.
Low and behold, my GTAIV game has booted up successfully since I've disconnected these two things and with no problems.