Followed instructions to a T. New battery would cause reboots and CRC errors in the logs every 3 minutes or so.
Turns out the battery I got on eBay for this is defective as it would not charge. After replacing it back with the original Apple battery, no more reboots. I noticed the new battery was not charging as there is no lightning icon in the battery bar on the iPhone 4 screen when it was plugged into the adapter, it only showed that it was plugged in. The original battery has a lightning bolt icon in the battery bar, indicating it's charging when plugged in.
Thanks iFixit! Great instructions! Too bad my replacement battery from eBay does not work...