Sounds like a weird one. might not be applicable, but are you running your plugins as a different user (ie: nagios user)? have you tried switching to your nagios
user and then running the exact commands from your checkcommand definitions (but replacing the macros with the proper values)?
You should also try tailing /var/log/secure on the remote box to see if it's generating an error when nagios runs check_by_ssh on that host
other than that...just googled the problem and some other people seem to be having the same problem. heres one of the links i saw:
mail-archive.com/nagios-user ... 18645.html
have you considered nrpe instead of check_by_ssh ?