Array and curve modifiers behave strangely
It was an origin related issue as suggested in the comments by MarcClintDion and cegaton.

What I did to fix it was:


Switched to edit mode with the curve selected;
Selected the first vertex of the curve;
Snap Shift + S > Cursor to selected;
Got out of edit mode;
Set Origin Shift + Ctrl + Alt + C >Origin to 3D Cursor;
Selected the plane; 
Set Origin Shift + Ctrl + Alt + C > Origin 3D Cursor.


Not sure if steps 6 and 7 are necessary.

Additionally because the generated road was getting crazy cambers in some parts I went to the curve's properties and set Twisting to Z-Up.