Hey guys.
First of all, thanks so much for the help, Finch. I'll try to outline my situation.
My brother bought an used iPhone 3GS 32GB. He asked me to set it up for him. It had iOS 4.1, and I have no idea if any unauthorized actions had been taken on the phone. It had a lot of crap installed, so my first step was to restore/update it. I downloaded iOS 4.3.3 (since I've read that iOS 5 has performance issues on anything below iPhone 4), connected it on iTunes and did a restore. I got an error saying my iTunes version was incorrect.
I then downloaded 4.1 (which is the SAME version as what was previously on the phone) and did a restore. I got error 1015 and the phone got stuck in restore mode/endless boot loop. Tried to restore again. Same problem. I found on Google a possible solution: restore again using the latest iOS version. So, screw it, I went for iOS 5.0.1. It DID complete the restore, but when I was going to activate the phone it kept saying "could not connect to the apple server", while my iTunes screen said "no SIM card". I assume one leads to the other: phone not activated means SIM card won't be recognized.
So I followed with an DFU restore, reinstalling the iOS5. After that, during activation, it said "could not scan for wireless networks", prompting me to connect via iTunes. Now, I don't want to use my own iTunes account, and I don't know if my brother has one, but the impression I'm getting is that Apple servers are trying to lock me out of my own iPhone...