Does anyone have any more specific information on whether they just called crypt(key,salt) or actually used a larger salt with a call to encrypt()? The crypt() function only takes a 12 bit salt which is marginally helpful against rainbow tables.
Because you're worried about attackers constructing four thousand rainbow tables?
You wouldn't need 4096 if the choice of the salt was non-random; some versions of Unix used the first 2 characters of the username. What's the space requirement for a single rainbow table?
I don't know, but none of what they did was even marginally useful against iterated password crackers, so, change your password.