does your binary have relative paths to files? if you are calling it from a different directory, then maybe your effective directory is still in your cgi folder, and so the binary program is looking for files there, instead of somewhere relative to itself. just a thought.
also, it looks like you've probably got this covered, but is it have something to do with the user? because most webservers use a different user (like 'nobody' or 'apache'), so you may want to make sure your webserver's user as the correct permissions.