After reinstalling the telepathy-haze package, there was still no option to add an AIM account to Empathy. Even after closing and restarting Empathy, the option was not on the menu.
After quitting Empathy again, I searched the running processes for telepathy:
$ ps x | grep telepathy
9370 ? S 0:00 /usr/lib/telepathy/mission-control-5
9738 pts/0 S+ 0:00 grep telepathy
Bingo, I need to kill mission-control-5.
$ killall mission-control-5
Upon restarting Empathy I was then able to activate my AIM account.