To any who may ever get a similar problem...
I was getting a "Return code of 126 is out of bounds - plugin may be missing" error when trying to run a simple perl script as a plugin on Nagios 2.10. Permissions, location, configuration, etc. - everything looked OK. After much frustration, I found that the perl script file was a DOS-format file (i.e. CR/LF line terminations) and I was running Nagios on Linux (RHEL 3). Nagios does not like that. Changing the line termination to LF fixed the problem.
Make sure your plugins have correct line terminations!
Chicago, IL, USA