Lo tengo mas o menos implementado pero me funciona fatal, me lo realiza muy rapido. Os dejo el codigo:
Edito: Esta solucionado en el ultimo post por si ha alguien le es de utilidad.
sprite.cpp
sprite::sprite(){
    ando=0;
    posx=0;
    posy=0;
    //partw -> ancho de cada imagen dentro del sprite sheet
    partw=60;
    parth=120;  // alto de cada dibujo del sprite sheet
}
void sprite::andar(){
    ando=1;
}
void sprite::parar(){
    ando=0;
    frame=0;
}
void sprite::avanzar(){
    if(ando){
        posx+=speedx;
        if(frame<2)
            frame++;
        else{
            frame=0;
        }
    }
}
void sprite::pintar(SDL_Surface *superficie){
    SDL_Rect ori,dest;
    dest.x=posx+partw;
    dest.y=posy;
    ori.x=partw*frame;
    ori.y=0;
    ori.w=partw;
    ori.h=parth;
    SDL_BlitSurface(img,&ori,superficie,&dest);
}main.cpp
while(!done){
    if(andando){
         personaje.avanzar();
    }
    //...Eventos
    //KEYDOWN
    case SDLK_RIGHT:
        personaje.andar();
        andando=true;
        break;  
    //KEYUP
    case SDLK_RIGHT:
        personaje.parar();
        andando=false;
        break;
