The user input device I'm using sends the change in position from the last packet, so the kinematic bodies do not necessarily move in small steps. Fast movement from the user means larger steps from one spot to the next. My theory on this is that it seems like bullet is treating them as though they are teleporting from A to B, instead of processing it as a movement from A to B. Is there any way I can get Bullet to treat this as a movement from one spot to another?
The thing with kinematic bodies is that you're a bit on your own if you want them to behave like physics-bodies (themselves get pushed by other objects or collide with other objects). Bullet will allow other objects to collide with the kinematics (if enabled) but doesn't really care about the other way.
So your teleportation observation is correct..
You need to manually verify that the space your kinematic object is trying to move through is and will be free of other objects, if you really want to use kinematic objects for this. You can use btCollisionWorld::convexSweepTest for this every time you want to move a kinematic body and only advance it as far as it goes without colliding. It won't catch the case with a very fast-moving sphere, but it sounds like that is not the real problem here.
Be aware that kinematic controlling conceptually is a can of worms, when you fix one problem, you will find the next one, not necessarily due to anything Bullet-specific.
It might be possible in your case to use rigid bodies instead of kinematic objects and let the user input steer them (check for discussions about dynamic character controller here).