ERROR: is not executable by (uid 1002:gid(1002 1002))
or if the check is manually run by root:
ERROR: is not executable by (uid 0:gid(0 10 6 4 3 2 1 0))
Bunches of searching online only found posts about this error for qmail. When one breaks open the source code for check_mailq, it appears to be a path error. It boiled down to if Postfix is not installed when you compile the Nagios Plugins, it doesn't find the path for the Perl script. Since Posfix was now installed, I just needed to recompile the Nagios Plugins. Poof, check_mailq now works.