Also mich wundert die angezeigte Fehlermeldung. Zum einen ist es eine Apache-Seite. Wenn das über die index.php laufen würde, müsste doch die WordPress-404-Seite kommen?! Außerdem steht dort "The requested URL /2009.jpg/06/12/unboxing-des-neuen-iphone-3g-s/ was not found on this server.". Woher kommt das ".jpg" in der URL? Steht das so in der Permalinkstruktur drin?
Wenn die Permalink-Strktur korrekt gespeichert ist, solltest Du vielleicht noch sicherstellen, dass der Inhalt der .htaccess auch stimmt. Hast Du Plugins laufen, die sich da vielleicht noch verewigt haben? Und auch interessant wäre, was WordPress selbst für Links generiert, z.B. die Links zu Archivseiten. Entsprechen die dem gleichen RUl-Schema und führen auch zum 404?
Ansonsten: Hat Dein Hoster ein Forum, wo Du vielleicht nach Erfahrungen anderer Kunden mit WordPress auf den Servern fragen könntest?