On a related note, I also solved the problem on Windows. I'll post it here, in case anyone makes the switch from UltraEdit to Sublime Text and has the same problem.
It appears that UltraEdit associated many extensions with itself, and after an uninstall did not quite remove them. Then I got the following situation (see attachment). Sublime Text would not associate with any of the extensions, the association with "Unknown application" remained.
I resolved it by using "Unassoc, An Utility to Unassociate File Types in Windows 7 and Vista": http://www.winhelponline.com/articles/2 ... Vista.html
In Unassoc, I searched the extensions and pressed "Remove file association (User)". After that, I could associate them with Sublime Text without any problems.