After a couple hours of fiddling around and troubleshooting, I finally came up with a solution:
On the old laptop:
- Open Fireworks and go to Help -> Deactivate...
- Complete the deactivation process.
- Uninstall Fireworks.
- Move the "/Library/Application Support/Adobe", "/Library/Application Support/FLEXnet Publisher" and "/Library/Preferences/FLEXnet Publisher" folders somewhere else (you probably should keep them around somewhere just-in-case everything goes bad).
- Install Fireworks.
- Open Fireworks. It should ask you for your license key, and work!