Original iPhone needs to be hacktivated using Redsn0w or using a custom "pwned" firmware. Redsn0w, from what I've read, only works with firmware 3.1.2 whereas you should be able to find a custom 3.1.3.
Redsn0w should be fine even if device is on 3.1.3. Just have to use a 3.1.2 ipsw is all, but it will work on a device that is on 3.1.3 as well as 3.1.2. Redsn0w 0.9.4 is the version iPhone 2G needs for 3.1.3/2