Well, this was unexpected. It's been weeks after my friend and I gave up on registering this Kindle and I contented myself with using it offline (already read 4 novels so far). Just now, I turned on the wireless and opened the Store on a whim. It loaded on the first try with no error message at all. So I went to Settings and attempted to register, and this time, it worked
Maybe it just took some time for Amazon to sort things out.
Thanks everyone!