I just tried restoring a 250MB database from a backup on my local machine, and got the following message:

TITLE: Microsoft SQL Server Management Studio Express
------------------------------

Restore failed for Server 'MULTIVIS-A0D9F3\SQLEXPRESS'.  (Microsoft.SqlServer.Express.Smo)

For help, click: http://go.microsoft.com/fwlink?ProdName=Microsoft+SQL+Server&ProdVer=9.00.3042.00&EvtSrc=Microsoft.SqlServer.Management.Smo.ExceptionTemplates.FailedOperationExceptionText&EvtID=Restore+Server&LinkId=20476

------------------------------
ADDITIONAL INFORMATION:

System.Data.SqlClient.SqlError: CREATE DATABASE or ALTER DATABASE failed because the resulting cumulative database size would exceed your licensed limit of 4096 MB per database. (Microsoft.SqlServer.Express.Smo)

For help, click: http://go.microsoft.com/fwlink?ProdName=Microsoft+SQL+Server&ProdVer=9.00.3042.00&LinkId=20476

------------------------------
BUTTONS:

OK
------------------------------

I had 3 db's on the machine, one ~4.1gb db and two other dbs < 10mb each. So I did some googling on this error and saw the suggestion to try shrinking my other dbs to free up some space. So I did so on the 4.1gb db and now when I go to 'properties' for that db it says it is taking/using ~2.4gb. So I should have space now I figure, but whenever I try to restore the ~250mb database now I still get the error message above.. I tried restarting as well but that wasn't helpful.

Any idea what the issue is?