GPS phones aren't necessary because the cell phone tower positions are known. Your cell phone periodically checks in with nearby cell phone repeaters to say: "Hi, here I am if I get a call", and the repeaters can measure the signal strengths to triangulate. All that's needed is to subtract the time between two repeater check-ins to determine an approximate travel speed and direction. GPS phones though would add the capability of tracking side-street traffic flow.
AT&T could offer this service just with a software change on their central servers. The capital investment would be low and the benefits immense, at least to AT&T subscribers. If everyone had good real-time traffic data though, all travel route options would become about equal.
The 2G iPhones (the first model) already use that technique for a quasi-GPS location... but the accuracy is far less than what would be needed to determine travel speed and direction. In many areas, it is capable of locating you with in a one mile radius... in others, it's capable of getting it down to about 500 feet.