Та же проблема. Не помню, как именно решал, но, скорее всего, полной очисткой данных и синхронизацией с нуля. Я вообще несколько разочаровался и в сервисе, и в приложении. Сервис достаточно неудобный (не хватает разной сортировки песен и альбомов, например). Приложение постоянно глючит. Кроме синхронизации замечены были многочисленные глюки с проигрыванием — иногда зацикливается на одной песне, пока не передернешь pause/play. Иногда просто останавливается самостоятельно и опять нужно отжать паузу, чтобы пошло дальше. Вобщем, проще закачать нужное в девайс и слушать оффлайн.
