I have had a similar problem (albeit with a Powerbook) and I had to change my DVI-VGA (back then we didn't have Mini-DP). It was working until one day it simply stopped working. Since I had a lot of displays at home, I tried -like you- different cables and displays to no avail until I found another adapter and boom, it worked.
Another way to test this is go to an App Store or similar with your machine and your cable. Try to make it work there. If it doesn't, they will have extra adapters to rule out that possibility. If a new cable, display, adapter also fails, then your Mini-DP port could be failing and that requires an App Store anyway…
Since the mouse pointer gets frozen, you can be pretty confident that the lockup is happening deep down in the system - kernel extensions, hardware interrupt type things.
Assuming you have a great backup and don't mind futzing a bit (and I'll also assume you haven't extra cables, monitors, macs to just eliminate one thing at a time) you can surely try booting again in Safe Mode.
To boot in Safe Mode, hold the shift key down - it will bypass all non essential kernel extensions and may or may not help you isolate the issue.
It's best to be systematic when troubleshooting - so I'd try that one guess, then be more logical about it.
Why not start with the "bible" on Isolating issues in Mac OS X?
Don't forget you get 90 days of support from Apple - you can hit them up on AppleCare (800-APL-CARE or online - express lane) - they have a standing exception for people that cover software purchases for support - even if your hardware is out of the free software support timeframe.
The wisdom to isolate software before hardware is probably the best call here - even though it's a monitor and clearly buggy. What are the odds that Lion and the hardware failed at the same time? It's possible and you might be able to take your Air to another monitor with your adapter / cable and rule that out.
Good luck, and happy hunting - partner!
Best Answer
A few steps to try:
Try a different cable
Try a different screen
Try a different laptop/macbook
If you get success with one of these then the problem probably lies with whatever you left out, after that you'll have to try combinations of the above.