Interesting. I didn't know about that limit. While I only have a 4x20 LCD, I declared lcd.begin(16,1), and (16,4) and it seemed to work fine.
As it stands right now the LiquidCrystal library does not do much with the information it gets from the lcd.begin function. It does not use the column information at all and it only checks to see if the row information is '1' or something other than '1'. The default (if lcd.begin is not present) is, unfortunately, '1'.
The problem with the 16x1 devices is that most of them are actually 8x2 internally. So if your 16x1 doesn't display anything on the right side (with any LCD library) then try treating it as an 8x2. The problem with the 16x4 devices is that the initial addresses for lines 3 and 4 are different than the initial addresses for the same lines on 20x4 devices. Check out the LCD Addressing link at http://web.alfredstate.edu/weimandn for more information.
I doubt that your 20x4 device worked at all on lines 2, 3 or 4 when using lcd.begin(16,1). You should also have noticed a difference in contrast on line 1.
Don