There is a bug in the sort algorithm that does not take into account the custom fields and also will incorrectly sort if an invalid value is set in 'sortby' and is passed to search.php in $_REQUEST
This has been a problem for a while (since at least 2.5.3 core release and is still a problem in 2.5.5 and 2.6 core branches).
Patch file is attached.
Profile search.php sort bug
This is corrected, thank you
Fixed in SVN and waiting for review
Also included in XOOPS 2.5.7 Beta 1