Here are some potential issues or reasons fro your dilemna:
Is the "full" dropbox account the same as the one you deleted files in (hey, you never know)? is it the same folder? (potential duplicate?)
Despite deleting many files, your dropbox folder exceeds your account limit. Try right clicking the dropbox folder and clicking properties to check the size of the folder. Your account limit can be found on the website or on the dropdown menu in the desktop app
Your dropbox folder may not have sync enabled or similar settings that say something like "delete only on this device" or the like
Do you have shared folders? they take up space for bot the person sharing and the person shared to (links dont count, just the actual folders)
If all else fails, i suggest describing more of your issues and the things you tried to do, or sending a support ticket.