Had the same problem, and this worked for me.
I fixed it by installing 'lame'. Just open your terminal, type a command to get 'lame' (it's different for each Linux version), and that should do it. It's pretty straightforward and worked well for me.