I would just use /[aąAĄ]/ instead of just /a/ in patterns that you're using.

Besides that, have you tried use locale?

And you should remember to set LC_CTYPE or LC_ALL beforehand...

Also, question about tr... could be solved using extended regexpes, that is - you match a class of chars, and for replacement you call routine that replaces this with correct char. This solves multiple passess problem.