I just updated to 10.8.3, and yes, contacts now print out alphabetically! We knew that eventually Apple would fix the problem. I guess the saying that good things come to those who wait is true!
Thanks for the heads up about the update. I might have forgotten to try printing the contacts if you hadn't posted your message today.