What way did you remove the old database, did you just Drop the tables or compleatly remove the named database .

Did you remember to edit your config.php file after creating the new database, if your still having the same problem, its possible the config.php file is still pointing to the old database.

$dbhost = "localhost"; ( for Yahoo hosting services this is just "mysql" & not "localhost" other providers my varay)
$dbuname = "YOUR USERNAME FOR THE DATABASE"; (Usually same username for entering phpMyAdmin Panel)
$dbpass = "YOUR DATABASE PASSWORD"; (usually same for entering phpMyAdmin Panel)
$dbname = "YOUR DATABASE NAME";
$prefix = "nuke";
$user_prefix = "nuke";
$dbtype = "MySQL";