Mira no he probado tu codigo en mi servidor, pero el mysql_query no esta bien definido, seria asi:
Código PHP:
<?php
$db = mysql_connect('localhost','prueba','clave') or die("No se puede establecer la conexión con la base de datos");
$consulta = "CREATE DATABASE agenda";
if (mysql_query($consulta, $db))
print "<p>Base de datos creada correctamente.</p>";
else
print "<p>Error al crear la base de datos.</p>";
?>
El orden de los parametros es inverso al que vos pusiste. Primero va la cadena y luego la conexion (aunq este ultimo es opcional).
Probalo ahora, te funciona?
Saludos.