Here's what I did with header PCF8833.h to get the lcd to work on a mega, the backlight and reset pins whilst called the same thing aren't assigned to the same ports 'under the hood' + the SPI pins are 'jumbled'.
Compare the AVR_ATmega1280 ifdef and define with the bottom 1/2 to get an idea of how to do the reassignment to suit you, use this http://spreadsheets.google.com/pub?key=rtHw_R6eVL140KS9_G8GPkA&gid=0 as a reference for the pin assignments. See below the code for an untested idea of what you need to look at for a start.
/*Added ifdef to allow the shield to work directly on a normal arduino mega board
with the SPI pins broken out, Set RESET and BL_PINS according to your LCD wiring */
#ifdef __AVR_ATmega1280__
#define CS 53
#define CLK 52
#define DATA 51
#define RESET 9
#define BL_ON 8
#ifdef PB1
#define LCD_CS(x) PORTB= (x)? (PORTB|(1<<PB0)) : (PORTB&~(1<<PB0))
#define LCD_CLK(x) PORTB= (x)? (PORTB|(1<<PB1)) : (PORTB&~(1<<PB1))
#define LCD_DATA(x) PORTB= (x)? (PORTB|(1<<PB2)) : (PORTB&~(1<<PB2))
#define LCD_RESET(x) PORTH= (x)? (PORTH|(1<<PH6)) : (PORTH&~(1<<PH6))
#define LCD_BACKLIGHT(x) PORTH= (x)? (PORTH|(1<<PH5)) : (PORTH&~(1<<PH5))
#else
#define LCD_CS(x) PORTB= (x)? (PORTB|(1<<PORTB0)) : (PORTB&~(1<<PORTB0))
#define LCD_CLK(x) PORTB= (x)? (PORTB|(1<<PORTB1)) : (PORTB&~(1<<PORTB1))
#define LCD_DATA(x) PORTB= (x)? (PORTB|(1<<PORTB2)) : (PORTB&~(1<<PORTB2))
#define LCD_RESET(x) PORTH= (x)? (PORTH|(1<<PORTH6)) : (PORTH&~(1<<PORTH6))
#define LCD_BACKLIGHT(x) PORTH= (x)? (PORTH|(1<<PORTH5)) : (PORTH&~(1<<PORTH5))
#endif // End of PB1
#else // Every other arduino that this library worked with
#define CS 10
#define CLK 13
#define DATA 11
#define RESET 9
#define BL_ON 8
#ifdef PB1
#define LCD_CS(x) PORTB= (x)? (PORTB|(1<<PB2)) : (PORTB&~(1<<PB2))
#define LCD_CLK(x) PORTB= (x)? (PORTB|(1<<PB5)) : (PORTB&~(1<<PB5))
#define LCD_DATA(x) PORTB= (x)? (PORTB|(1<<PB3)) : (PORTB&~(1<<PB3))
#define LCD_RESET(x) PORTB= (x)? (PORTB|(1<<PB1)) : (PORTB&~(1<<PB1))
#define LCD_BACKLIGHT(x) PORTB= (x)? (PORTB|(1<<PB0)) : (PORTB&~(1<<PB0))
#else
#define LCD_CS(x) PORTB= (x)? (PORTB|(1<<PORTB2)) : (PORTB&~(1<<PORTB2))
#define LCD_CLK(x) PORTB= (x)? (PORTB|(1<<PORTB5)) : (PORTB&~(1<<PORTB5))
#define LCD_DATA(x) PORTB= (x)? (PORTB|(1<<PORTB3)) : (PORTB&~(1<<PORTB3))
#define LCD_RESET(x) PORTB= (x)? (PORTB|(1<<PORTB1)) : (PORTB&~(1<<PORTB1))
#define LCD_BACKLIGHT(x) PORTB= (x)? (PORTB|(1<<PORTB0)) : (PORTB&~(1<<PORTB0))
#endif
#endif
// PB5 = clock (SCK)=13, PB2 = SS (CS)=10, PB3 = data(mosi) = 11, PB1 = reset =9, PB0 = backlight = 8
// PB1 = clock (SCK)=52, PB0 = SS (CS)=53, PB2 = data(mosi) = 51, PH6 = reset = 9, PH5 = backlight = 8
I believe you will need to change this line:
#define LCD_CLK(x) PORTB= (x)? (PORTB|(1<<PB1)) : (PORTB&~(1<<PB1)) // for the mega
or this line:
#define LCD_CS(x) PORTB= (x)? (PORTB|(1<<PB2)) : (PORTB&~(1<<PB2)) // for the 168/328 boards
and this define:
#define CS 53 // 53 on the mega/10 on the 168/328
So if you wanted to make the CS pin analog 3 on a duemilanove (using the analog pin 3 as a digital pin) it would be:
#define LCD_CS(x) PORTC= (x)? (PORTC|(1<<PC3)) : (PORTC&~(1<<PC3)) // PORTC/PC3 for the 168/328 boards
and for the mega:
#define LCD_CS(x) PORTH= (x)? (PORTH|(1<<PH0)) : (PORTH&~(1<<PH0)) // PORTH/PH0 for the 1280 mega boards
And for either board:
#define CS 17
Please excuse my scrappy attempt at the ifdef for the 1280, it was my first attempt and it works for me, that was the main object of changing things, i also had issues with the PB/PORTB definitions too between boards, It'd would be nice to know if I got things right or how to correct it if not.
I'm really not sure why the CS,CLK and DATA #defines are there, they don't seem to be used at all it seems like the author was maybe exploring alternative methods for banging the data out to the screen.
You may also need to keep any eye on the spi registers to see if one lib is occupying the bus, you don't want to start sending data while the CS line is still active for the LCD and vice versa which is what is happening for you at the moment on top of both devices sharing the CS pin.
The nokia LCD library doesn't check the state of the registers it just switches the CS pin and starts sending data, the SDout pin from the PCF8833 isn't connected to the arduino so it doesn't wait for any data back either, so thats one issue to not have to worry about, I haven't looked at the ethernet code but I would take a guess and say that its running on an interrupt, so you may have issues to deal with there too.
Let me know if any of that helps or if you discover anything else.... 
Oh, one last thing the backlight pin (digital 8) could be tied to 5v to free up the pin. Of course whether you break out the backlight pin or not you will have to breakout the CS pin on one of the shields, (lcd I guess as its the top one), this could be done with a 8xsingle track bit of vero board, some long legged female stack headers and pins/headers to suit, with the bonus of getting extra gnd pins and SPI pins for other devices.
Erm, this really is the last thing... If you breakout the backlight pin you can dump it onto a pin with PWM (err, like pin 9......) to give you brightness control, no real reason they didn't do it on the 168s and I'm not really sure why they put the reset button on pin 9, it can safely be disconnected and could be re-routed to the arduino reset pin. the design of the LCD shield needs a little rethink IMHO as it only uses 4 necessary pins (data,clk, cs and analog 0 for the joystick) but blocks access to all the other pins 
Regards,
Reggie.