Fuze Frozen! 'Not Enough Space For Music DB'?

Format the whole device and start fresh I would atleast try that before I send it way