technik, I would check the step pulse signal (with a scope if possible) to see if it is getting high enough. It sounds to me like it's on the harry edge of failing to be seen at the PIC and when you increase the PIC's supply, that shifts the voltage level where a signal is seen as a 1 vs a 0. You might have a PC with a "weak" parallel port (still in speck, but not driving the pins as hard as most) or a bad connection on the BOB or other connector. Also the timing setup in your CNC software may need to be adjusted so it produces a longer pulse, giving the parallel port drivers time to pull the pin to the correct level. If you find that's the issue, you can also adjust the value of the pull down resistors on the Linistepper board to adjust.
Or it could be something totally different. I'm a software/firmware guy, not an electronics engineer at all.