While programming MCLR does not need to be connected to anything but the programmer.

Do you have MCLR configured as an input or reset?

This may also help.
http://www.melabs.com/support/icsp.htm