Sorry, missed your update with the pics.
The wiring looks correct. The speed and contrast issues sound strange though.
Just to be safe, disconnect the wires that go to the LCD. The worst-case scenario would involve 5v signals getting through to the output pins, and even though I'm not sure how that would happen, I'd rather not learn the hard way.
Once you've done that, let's do some basic debugging: check the voltage between the rails to confirm that it is indeed 3.3v.. a regulator failure on the Arduino is theoretically possible. Check it both at the rails and at the VDD/VSS pins of the chip.
Next, write a simple sketch that sends all the pins you're using LOW for 3 seconds, then HIGH for 3 seconds. The goal is to check the input and output voltages for each buffer. If you have two meters, this would be a perfect time to break them out.. connect one to the input pin and one to the output pin. If you only have one meter, the 3s window should give you enough time to get readings from both.
As simple as this chip is, any failure should be pretty easy to see.
When you void a product warranty, you give up your right to sue the manufacturer if something goes wrong and accept full responsibility for whatever happens next. And then you truly own the product.