Exporting is your problem. '$a' and '$b' are package variables to your package, but you (presumably) are sorting in package main. While sorting, '$main::a' and '$main::b' are set, but '$package::a' and '$package::b' are not, which is what the subroutine is using. I'm not sure what the solution is yet, but that's your problem.
Update: Well, I had things slightly backwards not having seen your example above, but glad I helped. Its still rather an ugly solution though having to put the package name in the sortsub thats in the main package... Wish there were something better :-(