MySQL - Problema con subquery

Hola,

Aprovechando la capacidad interrelacional de las bases de datos cree dos tablas, una llama paises que contiene un Id y el nombre de los paises

CREATE TABLE paises(
id INT(11) UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
pais VARCHAR(100) NOT NULL DEFAULT ''
);

La otra tabla es:

CREATE TABLE usuarios(
paisid INT(3) NOT NULL DEFAULT 0,
apellido VARCHAR(60) NOT NULL DEFAULT ''
);

En la tabla usuarios, ingreso en vez del nombre del pais, solo el id, el problema me surge cuando quiero recuperar la información, y cuando quiero ordenarla según el pais, ya que si consulto directamente me devolvería el ID y no el nombre del pais, por esto hago un subquery:

SELECT apellido,(SELECT pais FROM paises WHERE paises.id=paisid) AS nombrepais FROM usuarios ORDER BY nombrepais ASC;

Aparentemente el subquery se ejecuta una sola vez, inclusive utilizando SQL_NO_CACHE, probablemente esto sea así pero alguien conoce una solucion, es un programa en PHP.

O se le ha planteado un problema parecido, debo hacer si o si todo en una consulta porque sino no podre ordenarla, no?

Saludos y Muchas, Gracias