[Mike Copioli]

Without seeing your code I can only speculate based on my experience with PID. It sounds to me like you have a math issue and or a coding issue. If the system becomes unstable(oscillates) when you increase p gain, it usually means that the system is approaching the desired target and then overshooting. In your case the target is velocity. My advice is to not add any other gains until you have confirmed that your target velocity and current velocity are correct. The fact that when you increase P gain your system overshoots tells me that this is the case.