OK, so I started experimenting with pullups and pulldowns. First I replaced the 5.6K pullups with 220K pullups (I didn't have anything in between 5.6K and 220K). Nothing has changed really... Then I took out the pullups and replaced them with 5.6K pulldowns (instead of having the resistors between the gate and the 5V I put them between the gate and the GND). The situation became worse. Now all the planes are lit all the time.
Some interesting things I've noticed:
1.When I plug in the cube, but the Arduino is not connected, it starts up with all LEDs off. But if I put my hand near the 5V rail (I don't touch anything, I just take it 1-2 cm close tot he 5V rail), the LEDs start lighting up. The closer my hand, the more LEDs light up. I take my hand away, the LEDs go off...
2. When I unplug the cube, the LEDs stay on for 5-10 seconds (Depending on homw many are lit up). I guess that's because the power supply has some capacitor in it...