It's not so much a Nagios problem, as a permissions problem. I don't run check_nrpe in my environment, so I can't even test it. Nor do I run sudo, which is the alternate way.
When check_nrpe runs on your remote system (the one with qmail), it runs as a specific user. The fastest and easiest solution is to add that user to the group which owns the qmail/queue directory.
Depending on your installation, it might vary. I run a Gentoo system, so my directory is located at /var/qmail/queue. The group associated with this is called "qmail". By adding the nrpe user to that group your command will function. You will have to decide if that is a wise security thing to do or not.
The alternate is to set up a sudoers file, and grant the nrpe user access to a script with no password (and no tty). These scripts will contain a line something to the effect of:
/usr/bin/sudo /usr/local/nagios/libexec/check_qmailq -w 10 -c 20
(Security hat: If you EVER do any script as root, always use full paths for everything. If you are lazy, you will pay.).
Then you call that script as your check, not check_qmailq.
Hope that helps you get in the right direction.