In the Joomla admin area, go to Help -> System Info. Then click on Directory Permissions. All directories there should show up as green. Take specific note that the Temp, Log, and Cache directories are all real directories, and also are marked as writable.
Hopefully that's all it is, but if you still have issues, just let us know!
That's definitely the issue then. While 755 for permissions is a good general guideline, each server is different as far as the 'owner' of files, which user is running Apache, what permissions PHP has, etc. It may be necessary for permission of 775 to install. It's even possible that you may need to make those directories 777 (fully writable by anyone) to install. If you do that, we highly recommend changing it back to a more secure mode after installation is complete.
The only other option I know if is to enable the FTP layer in the Global Configuration -> Server area. This will enable a new installation box on the Install/Uninstall screen to allow Joomla to write to your filesystem through FTP instead of directly. It's a bit roundabout, but it's been known to work.
Unfortunately, we don't have anyway of getting around those problems within our extension. If Joomla's reporting the directories are unwriteable, that means the problem is 'above' us.
Hope that helps and explains the issue!