After a couple of failed stabs at testing the relative speed of window.localStorage versus client-side databases, Ryan Grove and Can Duruk pointed out that my tests were not taking into account the asynchronous nature of the APIs. So, here is what I think is a more correct test of the relative speeds. Turns out it makes a huge difference when you test things correctly!
On my MacBook Pro in desktop Safari, I'm seeing the DOM storage test take ~0.1ms per set of operations and ~10ms per set of operations for SQL storage. At that speed, the difference would be imperceptible to end-users. However, on my iPhone 3G, I'm seeing ~1ms per set of ops for DOM storage versus ~140ms for SQL. Now we're talking about a difference users might notice. This test shows me it pays to carefully consider whether the extra power of SQL is worth the speed cost on meek devices.