Update:
I have gotten the sensor to work without level shifting it (as sda/scl are open collector). However it is very temperamental and will sometimes just not work at all. I also cannot get four devices to work, three will but not four. Again, this code and these devices work fine together on a Mega.
Does anyone have any experience with similar I2C problems?