The issue: The Arduino Mega has its SPI port mapped on pins 50 to 53, which is on the dual row header at the end of the board. Those pins are not accessible through are regular Uno shield.
To use my Video Display shield (and any other shield that wants to talk SPI), this is what I did:

Connect the SPI communication signals through jumper wires to the shield.

• SCK:   Mega pin 52  -> Uno shield pin 13 - orange wire
• MOSI: Mega pin 50   -> Uno shield pin 12 - brown wire
• MISO: Mega pin 51  -> Uno shield pin 11  - blue wire

The slave select pin 53 does not need to be wired, as it is mapped as a normal GPIO in a normal Uno sketch. The picture for the pin numbers 50-51 on the Mega connector is misleading due to the parallax. 

(The RCA connector is not in a ideal location for the wire jumpers. Here is a reason for another spin).

Make pins 11 to 13 on the Mega inputs or tri-stated outputs.

Add the define somewhere in the header file for the shield or at the beginning of the sketch

#define MEGA 

Add the code to disable the pins that are used by Uno for SPI in the setup() function

#ifdef MEGA 
pinMode(11, INPUT); 
pinMode(12, INPUT); 
pinMode(13, INPUT); 
#endif

 This was all I needed to do and the MEGA was happily configuring the Video Display shield and outputting the test patterns.

And the compile log told me, there is lots of memory available compared to the Uno:

Sketch uses 7498 bytes (2%) of program storage space. Maximum is 253952 bytes.
Global variables use 424 bytes (5%) of dynamic memory, leaving 7768 bytes for local variables. Maximum is 8192 bytes.

That was easy. (Edit: Well, to easy to not mess it up, pin numbers are now correct, see comments)