causing this issue. My guess would be a bad battery connection - you sure the new battery is fully charged? Do the car's hi and lo beam lights work? Did you measure the battery's terminal voltage?
Also inspect the ground connection just behind the battery's negative terminal. It's a bolt down point to the firewall -- often the battery cable freys there and the cable can't supply enough current to the car for hi powered things (like a starter - but you could get dash lights, etc)...