Can't play HD .mkv files (even in vlc)

I am not able to play any HD .mkv files in vlc. (No problems with low quality videos). Here for example,

It says "Unfortunately there is no way to fix this", really???

when the same video is played in Videos, I get this:

And.... this:

Some times I get a little bit different error messages (for a different video)

That goes like this:

Note:

1. In the first video, I can hear the audio.

2. I need to play these videos no matter which player. (Any video player )

3. Yes, I have Installed "Ubuntu restricted extras" with all optional add-ons.

Thanks.

EDIT:

After following this: How to install H.265 / HEVC codec on Ubuntu Linux? have installed vlc-plugin-libde265 and gstreamer0.10-libde265 gstreamer1.0-libde265.

Even after doing this, the second error (VP90,undf) still exists . But the first video is playing in a very bad way (green everywhere ) I have recorded it and it is here (Audio is not recorded but i can hear it)

Link to download one of the video which can't be played on mine is here checkout if it plays on your PC.

Output of apt-cache policy gstreamer0.10-libde265 gstreamer1.0-libde265 vlc-plugin-libde265 ubuntu-restricted-extras :

    vishwa@vishwa-PC:~$ apt-cache policy gstreamer0.10-libde265 gstreamer1.0-libde265 vlc-plugin-libde265 ubuntu-restricted-extras
gstreamer0.10-libde265:
  Installed: 0.1.12-1ppa1~trusty1
  Candidate: 0.1.12-1ppa1~trusty1
  Version table:
 *** 0.1.12-1ppa1~trusty1 0
        500 http://ppa.launchpad.net/strukturag/libde265/ubuntu/ trusty/main amd64 Packages
        100 /var/lib/dpkg/status
gstreamer1.0-libde265:
  Installed: 0.1.12-1ppa1~trusty1
  Candidate: 0.1.12-1ppa1~trusty1
  Version table:
 *** 0.1.12-1ppa1~trusty1 0
        500 http://ppa.launchpad.net/strukturag/libde265/ubuntu/ trusty/main amd64 Packages
        100 /var/lib/dpkg/status
vlc-plugin-libde265:
  Installed: 0.1.7-1ppa1~trusty1
  Candidate: 0.1.7-1ppa1~trusty1
  Version table:
 *** 0.1.7-1ppa1~trusty1 0
        500 http://ppa.launchpad.net/strukturag/libde265/ubuntu/ trusty/main amd64 Packages
        100 /var/lib/dpkg/status
ubuntu-restricted-extras:
  Installed: 60.1
  Candidate: 60.1
  Version table:
 *** 60.1 0
        500 http://archive.ubuntu.com/ubuntu/ trusty-updates/multiverse amd64 Packages
        100 /var/lib/dpkg/status
     60 0
        500 http://archive.ubuntu.com/ubuntu/ trusty/multiverse amd64 Packages

HEVC and VP9 decoders are missing on your system. To install VLC HEVC plugin try:

sudo apt-get install vlc-plugin-libde265

You could also try out MP4Client Player from GPAC.

Edit: GPAC will for sure play HEVC content but I'm not sure if it also supports VP9. Please ensure to install Latest available binaries from the GPAC site and avoid using apt-get install gpac in this case.

sudo apt-add-repository ppa:strukturag/libde265

sudo apt-get update

sudo apt-get install gstreamer0.10-libde265

sudo apt-get install gstreamer1.0-libde265

sudo apt-get install vlc-plugin-libde265