SQL Server Express installation fails

I'm having a problem installing either Microsoft SQL Server 2012 Express or 2008 R2 Express.

The installation starts and I choose "New installation...", I get to the step where I choose what should be installed, and it continues to the step where I specify the instance name, but when I click next in the step, I get an error popup saying:

SQL Server Setup has encountered the following:

Could not find the file.

Error code 0x84BB0001

Then it says the install crashed...

I used to have 2008 R2 Express installed prevously but had to reinstall it.

Now my guess was that there are files left somewhere, so I ran Windows Installer Cleanup Utility to remove anything related to SQL Server, but it still dosnt work.

What can I do to fix this? We're really looking for a solution for this.

Edit, copied from log just before the stack:

2012-09-20 12:07:00 SQLBrowser: CalculateUserNamePassword: SQL Server Browser service exists: retrieving current service account.
2012-09-20 12:07:00 Slp: Sco: Attempting to get start account for service SQLBrowser
2012-09-20 12:07:00 Slp: Invoking QueryServiceConfig Win32 API for buffer size
2012-09-20 12:07:00 Slp: Error: Action "Microsoft.SqlServer.Configuration.UIExtension.WaypointAction" threw an exception during execution.
2012-09-20 12:07:00 Slp: Microsoft.SqlServer.Setup.Chainer.Workflow.ActionExecutionException: Thread was being aborted. ---> System.Threading.ThreadAbortException: Thread was being aborted.

You have previously had an SQL Server installation. The installation correctly uninstalled, but left behind your databases. Unfortunately, SQL Server 2008 R2 (SP2) and SQL Server 2012 does not support installation over that data, which is especially obvious if the previous installation was a newer version than the present one in which case there is no way to downgrade the database schema versions.

Find your .mdf/.ldf files on the disk and remove the whole data folder.