I came across this error under Windows XP. (Don't worry, I'm just using it as my development site, not production.).
Environment: Windows XP, Apache-2.2, PHP-5.2.5, MySQL-5.0, WordPress-2.5
These were the steps which I followed to install Wordpress without it resulting in that nasty error message.
1. Install Apache
2. Install My-SQL. Note: in Wordpress' installation instructions this step comes after PHP installation. However, I read somewhere someone suggesting to install PHP after My-SQL. Don't know if this was the determining factor, but it was the way I took.
3. Install PHP. Here is were I think you'll make it or break it. When installing PHP,
a) be sure to point to Apache's conf directory when asked where its configuration directory resides, don't just point to Apache's install directory,
b) when asked which items to install, navigate down into Extensions and select MySQL and MySQLi. By default, these won't be installed.
4. Copy wordpress directory contents into Apache's htdocs directory (just my choice, but there are ofcourse other variations which will work).
5. Restart Apache.
6. navigate to http://localhost/wp-admin/install.php This time it should work.
I make no claims to being an Apache/PHP/MySQL/WordPress guru or even a dimly enlightened student. Some of the steps above are probably unnecessary, but they seemed the right thing to do, and hey - IT WORKED!
I hope this helps.