I just install sublime on Ubuntu 12.04 and came across the same problem.
I thought the problem might be Sublime not beeing able to write info to a folder.
I think I got a solution for the problem.
What I did was to start sublime from the terminal as superuser and then enter the registration key.
I've restarted Sublime several times and I'm still registered!
I hope this helps