thanks all for the replies.
I found the issue. It was indeed a wiring issue.
I was trying to control brightness and contrast using an IR remote control and for this I had wired V0 and A to pins 6 and 10 respectively, without having any resistors between the board and the LCD. I guess i was sucking too much current and the LCD went crazy.
Adding 220 Ohm resistors fixed the issue and I can now control brightness & contrast with the remote control. The LCD doesnt display random characters anymore.