"Cannot run program, permission denied": avr-g++

I use the Arduino IDE mostly in Windows. I once happened to install the IDE from the Linux-based distribution OS package repository and it worked.

I have been trying to get the official, downloaded version working in my Linux Mint (LIVE) distribution. When I try to run as "sudo sh /PathToIDE/arduino", it opens up and I can type the code. I however get this error when I try to compile the code:

Cannot run program "<PathToIDE>/hardware/tools/avr/bin/avr-g++": error=1.3, Permission denied

I am not sure why this is so since I run the executable as root.

Please help. I tried this with both 1.0.3 and 1.0.5.