Serial does not work when LiquidCrystal library is used

Question

I have been struggling with a LCD for 6 hours straight - I've had many problems including random characters showing up, and this time (not quite sure what changed, I tried so many things) as soon as I instantiate a LiquidCrystal object the Arduino stops sending on the Serial port. On the following code, commenting the instantiation of lcd makes "Starting" and "Printing" appear in the serial terminal - otherwise nothing is displayed. Either way, the LCD is desperately blank (black spaces on the entire first line, and I tuned the contrast when random characters were displayed).

// include the library code:
#include <LiquidCrystal.h>

// initialize the library with the numbers of the interface pins
//RS EN D4 D5 D6 D7
//LiquidCrystal lcd(2, 3, 4, 5, 9, A5);
//RW to GND, VSS to GND, VCC to 5V, V0 to wiper of 5V-to-GND 10k potentiometer

void setup() {
  Serial.begin(9600);
  Serial.println("Starting");
  //lcd.begin(16, 2);
}

void loop() {
  //lcd.setCursor(0, 1);
  //lcd.print(millis() / 1000);
  Serial.println("Printing");
}

I'm using this Arduino Pro Mini, and this LCD. Note that on the Arduino, pins 10 11 12 and 13 are used for a SD (which works), and 6 7 8 are used for a RS232 driver (which is disabled).

Honestly I'm sending a message in a bottle, I'm out of ideas...

The wiring is as explained in the code, I checked it 5 times and it is matching. There is a 10k pot on GND-VO-5V of the LCD, and I haven't wired the backlight.

Edit1: With the LCD active (all lines uncommented) I probed all LCD pins with a 'scope and when it is triggered in Normal, I can see that they all have a pulse every time the LCD is updated (I added a delay in the loop to make it more obvious). HOWEVER pins 9 and A5 take much longer than the others to get back to a high state, around 3 microseconds. Why? It might explain why the LCD doesn't work, but I don't see how it can explain the apparent freeze.

Edit2: Okay, I desoldered pins 9 and A5 and placed the wires on pins A2 A3 instead. The square waves are all square now, and the Serial works - no idea why. And back to square 1, as the LCD prints random characters now...