Moving the player back to the last known good position will result in the behavior you're experiencing; the player will remain some distance away from what he's about colliding with. To take an example: if your character is moving at 300 pixels/sec and they're 5 pixels away from a wall, the next collision occurs in 1/60th of a second. If your framerate is 60FPS, a collision will be detected in the next frame, and the character will be moved back to the 5 pixels away from the wall he was at before the collision occured. Certainly undesirable.
The method you hit upon should work (moving the player back by the size of the intersected rectangle), as long as you're calculating the amount correctly. The Separating Axis theorem is good for this (in that article, see specifically section 7, "Finding the MTV").
Another method you could try, not involving calculations: on collision, move the player backward in small timesteps (maybe even pixel-by-pixel) until he stops colliding with the wall. Then, you'll know a spot that is much closer to the wall where it's safe to place him. Less efficient, but easier to implement.
Yet another method is continuous collision detection. It's somewhat more complex in nature. You should be able to find some information on it by simply searching around for "continuous collision", but the basic idea is:
- Figure out when and where the next collision will take place.
- If the next collision will occur within the current timestep, move the object to the position where the collision takes place.
- If the next collision doesn't occur within the current timestep, just move the object forward its current movement speed.