Looking at their schematic...
<img src="http://www.olimex.com/dev/images/pic-pg2c-sch.gif">

PGM pin is left floating (sv3-3)... but you said you already tied it to gnd so it shouldn't be the problem... should

You said MCLR/VPP was close to 13Volts... so couldn't be this

So if the Software is not well done, this poor device programmer can't work properly. 18Fs are a little bit more tricky and noise sensitive..

Can you just try to use ICSP?

Something like ... (courtesy of Melabs)
<img src="http://www.melabs.com/images/icsp1.gif">