Thanks to everyone that responded - this has been very helpful.
So it seems that this _is_ locale-related: Hugh's explanation points out that not all two-byte strings are valid characters under UTF-8, and that would break 'tr'. Thus the change to 'C' fixing the problem. That really helped me understand the problem, thanks.
I want a command line solution, so GRC's website doesn't work for me. And I don't think it's a good idea to take a password from another source: it's unlikely GRC stores generated passwords and then tries to hack the associated IP or web browser with it, but isn't it better to do this yourself so only you know the outputted password?
As for 'pwgen', it has precisely the same problem as 'apg' - it's not installed by default as Stewart mentioned.
Someone asked what these passwords used for. We have to create accounts on many services (most of which don't support any authentication method except passwords) and give those accounts to other people to use. It's my intent that the recipient should change the password to something more to their liking. But many people don't: they just let their web browser memorize the password and then let us reset the password when they "forget" it by changing browsers. At least this way I know they have a relatively random and secure password to start with, usually much better than what they would have changed it to.