Here are some of the problems I had with the "The Real Price of Gasoline":

Improper externality attribution. The most obvious example of this one was the "improper disposal of cars and car parts" from section 4; this is obviously an externality of cars and not of gasoline. The acid test for this mistake is, "Could something else be taxed to get rid of the problem more efficiently?" For example, urban sprawl (another of the alleged costs of gasoline cited in the paper) would almost certainly be more efficiently addressed by property taxes than gasoline taxes (if in fact it needed to be so addressed -- I'm fairly sure that the listed costs of urban sprawl weren't *net* costs, in that they didn't include any of the benefits of urban sprawl).
Road congestion is an interesting case of externality attribution: traffic is a huge cost generated by driving, and I'm willing to entertain the possibility that twenty or so years ago a gasoline tax might have been the most efficient way of addressing the problem. However, it is very clear that not all driving contributes to traffic equally (some roads are never clogged; some only during certain hours), and the technology these days is more than good enough to deal with it directly.
An even more subtle case is air pollution. Carbon dioxide is an inherent output of the burning of gasoline, so it makes sense to treat any and all costs of carbon dioxide as an externality. On the other hand, all of the other gasoline pollutants aren't inherent: they depend on either the car burning the gasoline (newer cars typically pollute less than old ones), or on the specific blend of gasoline being used (which varies from country to country and state to state depending on regulations). Now, maybe it turns out that the best way to address these variables is through a blanket gas tax, but I doubt it. I don't have a reference, but I'm sure someone has proposed a system in which your car gets a rating during its annual inspection, and that rating determines the gas tax you pay.
Anyway, the paper is just riddled with improper externality attribution: subsidized parking, roadway de-icing, etc., etc.
Double counting. You can't count both the costs of climate change and the costs to insurance companies for climating change related claims. You can't count the cost of potential sudden price changes as a cost, especially in a paper that is arguing that we should double (or more) the price of gas! You can't count the higher prices non-gasoline users of oil pay (than they would in a world with higher gas prices) as a cost. And you can't count the parts of federal transportation infrastructure spending that are explicitly paid for by the federal gasoline tax.
Oligopoly effects. This one's tricky, but the principle is simple: if a government subsidy or tax break doesn't lower the price of gas, or isn't otherwise tied to the amount of gas sold, it isn't an externality of gasoline usage. Don't get me wrong, it is still probably bad, but a bad of the "government handout to the rich" rather than of the "something we should raise the price of gas to compensate for" form.
If gas was produced by a monopoly (call him Mr. OPEC), it's easy to see that granting Mr. OPEC a tax break wouldn't effect the price of gas at all: Mr. OPEC would just take the money and keep charging the same amount for gas. Similarly, if gas was sold in a perfectly competitive market, and the government decided to give a exploration subsidy to just one gasoline seller (call him Mr. Texaco), it's clear that again, Mr. Texaco just pockets the money and the price of gas is unchanged.
On the other hand, if the government gave a tax break to all the sellers in a perfectly competitive market, the price of gas would go down, as long as the size of the tax break that everyone got was at least roughly linked to the size of their market share.
As usual, the real world is somewhat in between: gas is produced by an oligopoly, and the U.S. government gives tax and program subsidies mostly to U.S. oil and gas sellers, in a way that is vaguely correlated with market share. My guess is that said subsidies are almost entirely ineffective in lowering the pump price of gas, but at the very least it is incorrect to count their full amount as an externality.
Military spending. There's really no way to calculate this impartially (did you know that almost all of the major oil companies opposed the Iraq war?), so let me just say that analysis under 3) applies: the military spending only counts as an externality as so far as it is effective in lowering the price of oil.
Ye Olde Pork barrel. An awful lot of the various federal, state, and local transportation budgets don't help anyone who isn't a politician or construction worker. It is thus not entirely fair to count their entire sum as an externality of gasoline use.

I could go on, but it's dinner time and I'm hungry. For the record, I think the major externality of gasoline use is increased damage, or chance of damage, from global warming. Sadly, this is hard to estimate and also depends a lot on how much you discount future costs (the Copenhagen Consensus papers on climate change are a good introduction to the issues). I've seen believable calculations stating that anywhere from a $20 to $200 per carbon ton tax might be optimal. That works out to only $0.06 to $0.60 per gallon of gas, but especially at the high end it would probably put coal out of business.