Saldan

Good news!  I've solved the problem.  The issue was that I should have been pushing a matrix created from the inverse of the Orientation (as well as reversing all the transformation data, i.e. the rotation and translation).  What I do now is

	//Rotate camera
	glMultMatrixf( m_PlayerCamera.GetInvertedMatrix() );

	//Translate camera
	sf::Vector3<float> CameraPos = m_PlayerCamera.GetPosition();
	glTranslatef(CameraPos.x, CameraPos.y, CameraPos.z);

Where GetInvertedMatrix() looks like this:

GLfloat* Camera::GetInvertedMatrix()
{
	//Get a new quaternion, the inverse of the Orientation
	Quaternion InvertedOrientation = m_Orientation;
	InvertedOrientation.Invert();

	//Fill the matrix with the orientation
	InvertedOrientation.RotationMatrix(m_RotationMatrix);

	//Return that matrix
	return m_RotationMatrix;
}

Once I do this, everything works as intended.

In case anybody in the future is looking for the way to Invert() a quaternion, here's my code:

void Quaternion::Invert()
{
	float Length = 1.0 / (x*x + y*y + z*z + w*w);
	x *= -Length;
	y *= -Length;
	z *= -Length;
	w *= Length;
}

So I'm working on a simple prototype that I want to use to learn about 2D random map scripting.  My ultimate goal is to include random map scripting in my current project, but before I get that far, I want to make sure I've got the basics down.  Unfortunately, I just spend four hours struggling to get a script that evenly distributes X players on a square map, and that's probably going to be the least of my troubles.

I've looked around on the Internet and found lots of articles concerning 2D cross-section fractal maps (à la Scorched Earth), 3D mesh generation, and Perlin noise, but none of these seem helpful.  Perlin noise looks popular for some applications, but it's very blotchy-looking and I'm not sure I can effectively use it to control the various parameters of the map.  Strangely, I've found very little documentation on the algorithms used in games like Civ4 or AoE (Age of Empires II being the particular game I want to emulate with this prototype).  I saw a single mention of flooding algorithms as being the basis of the RMS in Age of Empires, but it was only a fleeting mention and, having read the Wikipedia article on flooding algorithms, I'm not at all sure how they can help me in writing a random map script.

Can someone give me a basic breakdown of what a random map script would look like, one that can accept variable parameters for map size, number of players, number and width of rivers, lakes, number and size and spread of patches of trees and so on?  Terrain height is not something I want to get into for the purposes of this prototype.

Also, as a side note, what kind of mathematical/computational algorithms can you use to evenly distribute points throughout a given area?  I was trying to get my program to distribute X points (representing player start locations; X would be between 2 and 10) along the edges of the map, being located between 5 and 10 tiles from the edge.  It was extremely difficult and the end result still isn't as tidy as I'd like it to be around the corners.  I'm sure this has been done a lot, though, and much better than I have done.

All right!  So, I made a lot of changes with my code, mostly along the lines you suggested, and now I am able to play a 256x256 map with as little lag as a 64x64 sized map!  I've eliminated all instances of looping through lists of all tiles, except during initialization.  I no longer modify all tile positions when the player moves; I modify the positions of the tiles I need to blit, immediately before blitting them, by comparing them to the player's position in the map.  

Also, I adapted the code used to determine the view-screen to help mobs and projectiles detect collisions more quickly, by only making them check collisions with the tiles in a 3x3 square around their position, rather than all visible tiles (or, python forbid, all tiles in the game world).

This is great!  Now that performance is back to reasonable , I can move onwards with some more mechanics.#

For anyone else who ever happens upon this and wants to take a peek, here is the code I use for determining what tiles to blit; note that all objects (tiles, projectiles, the player, mobs, etc) have a self.screenPosX, self.screenPosY, self.mapPosX and self.mapPosY.  My game.orderedMap is a list of lists, with each sub-list representing a row or tiles on the map.  The tile's .updatePos() function just draws a new rectangle at the current position, for bliting.

#This is the new blitting code, for the map.
	startMapX = (player.mapPosX / TILEWIDTH) - (VIEWWIDTH / 2) - 2
	endMapX = (player.mapPosX / TILEWIDTH) + (VIEWWIDTH / 2) + 3
	
	startMapY = (player.mapPosY / TILEHEIGHT) - (VIEWHEIGHT / 2) - 2
	endMapY = (player.mapPosY / TILEHEIGHT) + (VIEWHEIGHT / 2) + 3

	xShift = player.mapPosX - player.screenPosX
	yShift = player.mapPosY - player.screenPosY

	for tileRow in range(startMapY, endMapY):
    	for tileCol in range(startMapX, endMapX):
        	if tileRow in range(len(game.orderedMap)) and tileCol in range(len(game.orderedMap[tileRow])):
            	tile = game.orderedMap[tileRow][tileCol]
            	tile.screenPosX = tile.mapPosX - yShift
            	tile.screenPosY = tile.mapPosY - xShift
            	tile.updatePos()
            	windowSurface.blit(tile.data["texture"], tile.data["rect"])