My guess is that some of the files required during boot up were deleted or corrupted or not closed correctly when it first failed to boot up due to no free space. Somehow you need to find which ones they are and replace them, either from the live CD or from backups you may perhaps have taken.
Knowing what files/directories to replace might take a lot of trial and error though.
I'm no expert on this but searching for "repair ubuntu installation" might give some clues.
sudo apt-get install --fix-broken
or this page: How to repair a broken Ubuntu Desktop installation - Karmic Koala — Dharwadkar's Home on the web
Can you boot into the 'recovery' mode from GRUB?
Bookmarks