It's possible you could have gotten a bad battery; it has temperature and voltage/current sensors built into it and if the phone can't read those sensors it will reboot as you're seeing.
There are a couple of things you can try. First of all, you can simply pop the original battery back in (or just plug it in without installing it) and see if the reboot still happens. If not, that would be pretty definite proof that your replacement battery is bad.
Otherwise, there's always a chance something else got damaged in the process of replacing the battery, but without more information it's impossible to say exactly what that might be. I'd suggest checking out the kernel panic wiki page in order to locate any panic logs that are present. If you find one, it'll tell us why the phone is rebooting and we can go from there.
[[iPhone Kernel Panics|iPhone Kernel Panics - iFixit]]
Either screenshot or copy'n'paste the first page or so of your panic log and add that to your question. At that point we should be able to figure out what's going on with your phone.
[guide|21499|Adding images to an existing question - iFixit Repair Guide]