Wiring : http://www.reefledcontroller.com/images/lcd_bb.png
This is how you were [u]attempting[/u] to connect the LCD to the Arduino, it does not show the connections that you actually are using. Specifically, it does not show if you interpreted the pin numbers correctly and it does not show if you simply just made a mistake.
Is it interference via power cables or magnetic interference via air ?
This is a very good possibility. You might want to start with some ferrite chokes on the 240 v power leads.
Your picture of the display is interesting and it could provide some clues if we knew what it is supposed to be displaying. Examples: (1) There are several '#' symbols in your picture. On the correct display does the same character appear in each of those locations, and if so what character is it? (2) The two bottom lines are very similar. Are they similar on the correct display?