Возможные варианты того, почему так происходит и что можно сделать:
1) Пробелы все-таки хранятся в базе как &_nbsp;, тогда и удалять из базы надо &_nbsp;. На всякий случай проверьте еще раз. Не исключен вариант, что при просмотре показываетя пробел, а хранится как спецсимвол. Попробуйте посмотреть не через PhpMyAdmin, а какой-нибудь утилиткой типа heidi или workbench
2) При выводе из базы пробелы заменяются на &_nbsp;, тогда надо не в базу лезть, а в php код, который отвечает за вывод, и убрать замену пробелов из него. Если там сильно замудрено и не хочется ковырять ядро, то можно написать свою функцию-обертку, которая обратно реплэйсит &_nbsp; на пробел