Both sudo 1.7.6p1 and 1.8.1p1 work correctly for me on RHEL6 using pam_tally2. Can you try one of those? You can find rpms at http://www.sudo.ws/download.html#binary - todd