I think I just found a fix that might help others too (read below).
I've also been having slow and erratic wake up from sleep on my Lion-powered brand new Mid 2011 MB Air 13" (core i7 model) that I purchased less than a month ago. I've had the frozen mouse issue described earlier in this thread, with wake up times oscillating between 5 and 20 seconds. I've never experienced the need to force reboot the machine though like others report, so I am feeling a bit lucky.
However, this is definitely far from the sweet "instant wake up" that I saw on MB Airs using SL when I tested this behavior at the apple store earlier this year. But curiously the wake up is as slow and erratic as the "not so instant wake up" on the early 2011 MBP (also running SL). Apple had this big marketing argument that the MB Air would wake up instantly and I noticed how noticeably slower the early 2011 MBP were at waking up. I found that very suspicious since both previous generation MBP and my wife's MBP from a couple years ago wakes up as instantly as the MB Air did even though it's old, uses a regular HD and runs SL or Leopard. For me that killed any credibility to the argument that "SSD drives would make your MB Air wake up instantly". I was more left wondering "*** is Apple playing at ?!?!"
Anyways, I tried the disk repair route like others described, but to no avail...
However: While testing the wake-up behavior on various machines earlier this year, I looked a bit closer at the power management options hidden under the hood and only accessible via a Terminal console, using the command "pmset -g". I had looked at the configuration for the "hibernate mode" of the early 2011 MB Air and MB Pro. The air had its hibernatemode set to "0" (fast but unsafe sleep/wake) and the pro to "3" (which means potentially slower wake and sleep as the memory is being dumped onto a disk image for a safe sleep in case of power loss; see "man pmset" for details). The big surprise though is my brand new MB Air had its hibernatemode set to "3"… and guess what ? switching it to "0" seems to help with the wake up times a lot! It doesn't feel as slick as on SL, but it is much improved. To try it for yourself, all you need to do is open a terminal window and type:
sudo pmset -a hibernatemode 0
(then type your password to authorize the change)
After that, make sure to save your work often when you get close to very low battery levels. I would be very curious to hear if this works for other people too.
To me, this seems to indicate that half of the "hibernate mode 3" behavior is not working right, and the system is trying to dump memory onto disk right away, instead of waiting for very low battery level.