Also noch mal von Anfang an.
Backup hast du via FTP und auch von der Datenbank gemacht, gut!
Aktuelles WP Paket (http://wordpress-deutschland.org/download/deutsch/) runterladen und entpacken.
Alle Dateien und Ordner via FTP löschen, außer den wp-content Ordner (da stecken deine selbst installieren Themes, Plugins und uploads drin) und evtl. falls vorhanden die .htaccess. Die wp-config.php soll man behalten bzw. sichern, damit man die gemachten Datenbank-Daten noch weiß 
Dann die neue wp-config-sample.php mit deinen Datenbank-Daten befüllen, in wp-config.php umbenennen und alle Dateien und Ordner inkl. wp-content Ordner aus dem entpackten Download-Paket neu via FTP hochladen.
Jetzt noch den Admin-Login aufrufen und die Datenbankänderungen durchführen lassen. Fertig!
PS: Für WP 3.0.4 brauchst du mindestens mySql 4.1.2 und selbst diese Version wirst du nicht mehr lange nutzen können. Spätestens ab WP 3.2 werden nur noch Versionen ab 5.0.15 unterstützt. Also könnte da schon der ganze Fehler liegen!
Vielleicht hast du ja die Möglichkeit eine neue MySql 5 Datenbank anzulegen und die alte gesicherte MySql 4 Datenbank dort zu importieren. Vielleicht macht das ja auch dein Hoster für dich, musst dir dann halt nur die neuen Datenbank-Daten für die wp-config.php geben lassen 