I too have been having problems with this and WordPress 1.5 - list_cats() partially works, in that it lists the items alphabetically, but my use of categories is a little more complex.
I'm using wordpress to maintain a film criticism website (www.filmforensics.com). In 1.2 I had two areas of categories: one a list of genres (comedy, drama, etc.) and one a list of letters of the alphabet, so that you could search on either. I used the 'child_of' option to sort them into the two sublists, but, with the same code, that no longer works. The parent of the alphabetical categories had ID 10:
<?php list_cats(1, 'all the films', 'name', '', '', 1, 0, 1, 1, 1, 'TRUE', '10', '', '', '', '', ''); ?>
...and this now lists all the entries, not just those under ID 10. Having said that, they are alphabetical!
Could it be changes in the version of php required?