Assuming this is running under Linux or some other OS with strace, I'd replace the call to the binary with strace -o /tmp/curseword.log -s800 ./binary arg1 arg2 (the curse word should be chosen appropriately for the length of time you have been struggling with this problem.) Then grep through the resulting log for the files that it is unable to find, and look to see how it is trying to access them and what error code it's getting back.

Assuming the worst case (namely, it accesses them with the expected relative paths and gets back ENOTFOUND), replace "binary" with a shell script that records its working directory to a log file before exec'ing the real, renamed binary with the given args.

If the problem remains a mystery, you might try checking the sign of the Zodiac under which the computer was first booted. Watch out, though -- it's easy to be fooled by OS reinstalls and calendar drifts.