It sounds like you have collision detection working fine. What you're asking about is collision resolution. To make the character continue moving in a valid direction, don't move him back to his last valid position. That will just freeze him in place in an unnatural fashion. Instead, move him along the wall's normal until he is no longer colliding with it. This will however require you to know more data about the collision than just whether it happened or not, but if you're using bounding boxes it won't be too bad.
So the red dots are the points at which the player is rendered, and the grey line follows the bottom-right corner of the player's bounding box. The player is moving in the x direction and the y direction, but when he hits the wall he is only moved back in the y direction, the x direction is not affected. As a result he will "slide" along the wall. Note that he is always moved up the exact amount required to get him out of the wall.