The Tax Foundation holds that any assessment that raises money in excess of what is needed to defray costs is a tax, not a fee.The issue arises here because the U.S. Embassy in London is exempt from taxes, but not fees. The city claims congestion pricing is a fee, but the embassy sees it as a tax.
The TF general definition above is not a bad rule of thumb, but is easily criticized. Which costs? Over what period? Costs for whom? The intention in the City-Embassy case is to relieve congestion (and its associated externalities), so prices are presumptively to temper (subjective) quantity demanded rather than cover accounting costs. The lottery raises revenue above cost, but it is hard to think of it as a tax.
My crude definition of "fees" is to use them as a synonym for benefit taxes, where the concept of deadweight loss becomes a bit murky. Benefit taxes most typically arise when the "tax" is tied to a particular service. Garbage collection, particularly if it is marginal cost pricing, is a simple example. For instance, the benefit-view of property taxation ultimately views the property tax serving this role when combined with zoning (the consequence of which is the absence of deadweight loss). This crude definition is also easily criticized. What constitutes a "service?" The services must also be "voluntary," and what does that mean? If gas taxes are solely for the purpose of road maintenance (and perhaps mitigating air pollution costs) then they are fees, not taxes. That would be a bitter pill to swallow.
Update: The Tax Foundation has another great post on this, this time in San Diego. In it, they describe fees as being tied to a particular service.