Do you know how I2C works? The only thing on I2C lines that can make the line go HI is the pull-up resistors. Every I2C device can only pull the line low to ground (to communicate a LO) or let it float (at which point the pull-up resistors pull the line HI). This is how I2C detects if there are collisions on the line, if devices release the line to communicate a HI but the line stays LO, then you know another device is trying to send a LO and therefore know there is a collision. NO I2C device can "send a +V" over it's I2C pins. It can only go high impedance or LO (pull to ground).
ANd since I'm pretty sure 3.3V is still high enough to be a logical HI, all you have to do is make the pull-up resistors go to 3.3V instead. The main thing now is...are there any pull-up resistors in your 5V devices? If there are, you gotta get rid of them and make sure that all the pull-up resistors are to 3.3V. If they are already there in your 3.3V devices then you're done because you only need one pull-up resistor per line. Adding pull-up resistors has the "parallel resistors is the same as a single smaller resistor" effect and is the same as using one pull-up resistor of a lower value which can cause too much current to flow through the device pins when they pull the line LO to ground.
BTW, regulators are used to supply power. You can't use them to reduce a 5V signal to a 3V signal (or anything else like that). They are too slow to follow the digital signal, and don't behave properly when the input voltage drops below Vout + Vdropout. THey tend to output something more like Vin-Vdropout in that situtation which isn't necessarily a logical LO unless your VIn is low enough.
FOLLOW-UP EDIT: I read around and it seems the NXT has no pull-up resistors. Also, most slaves devices also do not have pull-up resistors either because it is expected there may be more than one slave on the I2C bus. If each had it's own pull-up resistors the total pull-up resistance of the lines might be too low causing too much current to flow through device pins when they pull the line LO. It makes more sense to integrate the resistors into the master since there is *usually* one master per bus. But even then, it's not a sure thing. So for the most part, no I2C devices have any pull-up resistors and they must be provided by the user. So, basically, make sure there are no 5V pull-up resistors on the CLK or DATA I2C lines. And make sure there is one 3.3V pull-up resistor for SCL and SDA each. You will have to add them if they aren't present in some other I2C device you have connected to the line.
Hope this helps.