I have the same problem with lists not being sorted alphabetically. Neither Special:Categories nor Special:Specialpages sort correctly but Special:Allpages does. I'm running:
MediaWiki (/http://wikipedia.sf.net//): 1.4.7 PHP (/http://www.php.net//): 4.3.11 (cgi-fcgi) MySQL (/http://www.mysql.com//): 3.23.58-max
Can anyone suggest why this might be happening? (Not being very familiar with MediaWiki, PHP or MySQL I'm at a loss where to start looking.)
Thanks, Karen