JUst did a fresh install using the steps you listed (working as root). After everything was installed did a check on synaptic (as root) and for the first time everything went properly.
Added a new user and logged as that user and synaptic worked properly (again for the first time). Looks like something got fixed in the background as now it is all good to go.