No, frame rate should not affect the speed - the gameplay will hinge entirely on their video performance, which is disastrous (even if you limit the speed, you can't control people whose systems will run the game at half speed).
You're experiencing this problem because you did something wrong: Your update/render routines run one after the other as fast as possible, with objects updating on a per-call basis (thus when the call speed deviates, so does theirs).
A time-based approach
The correct way to do this is to update objects on a per-second basis.
Consider a bullet for instance: Right now it probably knows how much it needs to move per frame. You need to turn this into how much it moves per second. How you do that is actually not too complicated.
First, your bullet's going to be updated more than once per second, so we need to actually update it every few milliseconds. Each time you update your physics engine, a certain number of milliseconds have passed since the last update: this is called the delta time, normally dt for short. The dt is determined before updating all objects, then all objects update using the same dt in order to keep in synch. The dt is generally passed as an argument to each object in its update call.
In fixed-step physics, the dt is a fixed number, whereas in variable-step physics, the dt varies depending on the actual amount of time since the last update (hence their names).
That brings us back to your bullet. It's been told to update with a dt of 16 milliseconds, for a physics engine updated 60 times per second: if the bullet moves 12 metres per second, you move it
(16.0/1000.0) * 12.0 metres in this update.