I have got mostly the same issue but I wasn't able to install ffmpeg not gstreamer problem.
I solved MY issue this way
TO FIX THIS BUG!!!!
So the order of fixing ffmpeg installation.
1) Add repository sudo add-apt-repository ppa:n-muench/vlc
2) Run update and install VLC 2.0 sudo apt-get update && sudo apt-get install vlc (notice that you might need to run distro upgrade to install all neccessary dependencies for VLC 2.0 version.
3) install ffmpeg sudo apt-get install ffmpeg
After that I was able to install ffmpeg and all neccessary dependencies.
I have got mostly the same issue but I wasn't able to install ffmpeg not gstreamer problem.
I solved MY issue this way
TO FIX THIS BUG!!!!
So the order of fixing ffmpeg installation.
1) Add repository sudo add-apt-repository ppa:n-muench/vlc
2) Run update and install VLC 2.0 sudo apt-get update && sudo apt-get install vlc (notice that you might need to run distro upgrade to install all neccessary dependencies for VLC 2.0 version.
3) install ffmpeg sudo apt-get install ffmpeg
After that I was able to install ffmpeg and all neccessary dependencies.