The sorting in the addressbook is by the Japanese syllabic alphabet order, that's cause it was designed for the Japanese market and as such they don't use the Alphabet (as you know it) for their names.
You don't say how you converted your zaurus to English but at a guess, you'll find a file called addressbook.qm in /home/QtPalmtop/i18n/ja/ delete that file and restart qtopia and the addressbook will be in English -however that won't solve the ordering problem.
There was a "fix" around for the older Z models, but you'll have to search the forums for it as I can't remember where it was.
good luck
Stu