licensing

"Licensing for this product has stopped working" - Adobe CS3/CS4 on a Mac

Recently, I had to recover my iMac from a Time Machine backup and a hard drive replacement (my old drive flaked out—see how I repaired my hard drive here (video included!)).

Upon trying to open any Adobe Creative Suite 3 app (I use Photoshop and Illustrator daily...), I got the following error window:

Adobe Illustrator - Licensing for this product has stopped working

I was taken to this Adobe Support page, which suggests a variety of options for fixing the problem—all of which didn't work for me.