As I understand the hack, they still have to decrypt the old 40-bit key to relay which is not hard to do with a "rainbow table" of sorts. If so, the 80-bit encryption seems like it would help immensely. Do I not understand this hack correctly?
That is a different hack (not yet seen "in the wild") in which a fob with a 40 bit key is cloned. Turning off Passive Entry may not be enough to prevent the initial stage, where codes are collected from the car, because the car still transmits towards the fob for "Walk-away Door Lock" and probably, to detect if the fob is still in the car. One person can collect codes from the car and then from the fob. Once complete, the hacking device can act as a fob.
The exploit used in this video is an old one, that has been used against many types of cars which have passive entry. One person stands near the car, holding a device which will relay the car's transmissions to another person with the second device. The second device has a larger antenna and the aim is to relay the car's transmissions to the fob, over some distance. The fob responses (of whatever key length) are relayed to the device near the car and the car is fooled into thinking that the fob is nearby and unlocks. The fob is not cloned and only works if passive entry is enabled. This method is only used once to open and start the car - once the criminals have drive the car away, they would no longer be able to unlock or start the car.