"Perhaps I'll try overclocking. Do you think that would help?"
It will help, but not with PAL played at anything other then 50,75 or 100Hz.
"When I run at 1280x1024 at 75HZ, reclock is happy with PAL and turns green
Sounds like you have found the answer
"My question was really, should I be concerned if this Average Frame rate drops a little below 25 FPS with PAL if the movie appears smooth?"
If it looks good why worry.
"I understand there are some contraints with my hardware; but if Recklock will only sync up properly if the timing is a multiple of the frame rate (25HZ) it looks like I would still have this problem even if I threw more CPU power, etc at it, since my pj needs to run at 60HZ when using 1400x1050."
That's the unfortunate truth
"I'd be very interested in other peoples experiences of using Reclock and how it relates to the Average Frame rates they're achieving."
I have never paid much attention to average frame rate as long as it looks good. You almost never get exactly 25fps anyway. Same as you would not get exactly 30fps for NTSC source.
The ffdshow resize-sharpen dude