In the file MAX7456.cpp, look for this code starting at line 152:
// make sure the MAX7456 is enabled
digitalWrite(_slave_select,LOW);
MAX7456_spi_transfer(VM0_WRITE_ADDR);
MAX7456_spi_transfer(VERTICAL_SYNC_NEXT_VSYNC|OSD_ENABLE);
digitalWrite(_slave_select,HIGH);
delay(100);
Change the line
MAX7456_spi_transfer(VERTICAL_SYNC_NEXT_VSYNC|OSD_ENABLE);
to this
MAX7456_spi_transfer(VERTICAL_SYNC_NEXT_VSYNC|OSD_ENABLE|VIDEO_MODE_PAL);
Please report back if that solves the problem. I'm aware that lots of the world uses PAL, but I don't have any hardware to test with, so I haven't added code to switch to PAL mode. If this works for you, I'll try to add a PALL switch to the library.
-j