How do I troubleshoot a lockup that occurs when plugging in an external monitor?
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!