So I messed around today with my laptop and deleted the directory
/var/lib/aptitude/ (of course backing it up at first).
The next time I tried updating the package list, aptitude complained about the missing state file in this directory. At that time, I deleted the directory for good. A quick Google search revealed… exactly nothing.
In case anyone is as stupid as I was, here’s the really quick fix: recreate the directory, the state file will be created by aptitude, the directory however won’t.