I seem to be having the same problem.
When I log into my webmail (squirrelmail) I can send mail no problem. I sent mail to my gmail and it got there. However, when I try to send mail through my thunderbird e-mail client I get the relay access denied error.
This is odd because I've had no problems with this system for about a month since I initially got it running. Does anybody have any idea what within my client could be causing the problem? Thanks!