Mira un ejemplo simple que tengo hecho que simplemente dibuja un fondo que se va moviendo en una ventana de 1024x800 funciona como mucho a 35 fps así que en cuanto le pongo más cosas se suben mucho los frames.
El código es:
#include <stdio>
#include <stdlib>
#include <SDL>
#include <iostream>
using namespace std;
#define An 1024
#define Al 800
Uint32 ini_milisegundos, fin_milisegundos, frametime;
void ResetTimeBase()
{
  ini_milisegundos = SDL_GetTicks();
}
int CurrentTime()
{
  fin_milisegundos = SDL_GetTicks();
  return fin_milisegundos - ini_milisegundos;
}
int main(int argc, char **argv)
{
	int i, j, cont = 0, salir = 0;
	
	SDL_Surface *screen, *fondo;
	SDL_Rect rect;
	SDL_Event event;
	
	if(SDL_Init(SDL_INIT_VIDEO | SDL_INIT_JOYSTICK) < 0)
    {
      printf("No se pudo iniciar SDL: %s\n",SDL_GetError());
      return 1;
    }
  
    screen = SDL_SetVideoMode(An,Al,24,SDL_HWSURFACE);
    
    if(screen == NULL)
    {
      printf("No se puede inicializar el modo gráfico: \n",SDL_GetError());
      return 1;
    }
	
	fondo = IMG_Load("fondo.png");
	fondo = SDL_DisplayFormat(fondo);
	
	while(!salir)
	{
		ResetTimeBase();
		
		for(i=0;i<Al;i+=64)
		{
			for(j=0;j<An;j+=64)
			{
				rect.x = j;
				rect.y = (i + cont) % Al ;
			 
				SDL_BlitSurface(fondo, NULL, screen, &rect);
			}
		}
		
		cont++;
		
		SDL_Flip(screen);
		
		while(SDL_PollEvent(&event))
		{
	  		if(event.type == SDL_QUIT)
	    		salir = 1;
		}
		
		frametime = CurrentTime();
		cout<<"F:"<<1000/frametime<<endl;	
	}
}
La imagen que uso es (64x64): 
 
Espero que me podais ayudar.
Muchas gracias.
No molestar, programando ... XD