Ok quick check list:
1. on your surface you are using videos not smart glass?
2. In videos it says "signed in" at the top right?
3. Are you using the same account on you surface as you are on your xbox?
4. Xbox is up to date with the latest dashboard?
5. Settings on your xbox are correct?
System>Console Settings>Connected Devices> Then click the "on" option for "play to"
6. Are you connected to WIFI? (sounds silly but just make sure)
If you need a video to try download one of the MS press event files they are MP4.
Windows Newsroom: Windows 8 Video Gallery
If it still isn't working and you have a Lumia check and see if you can use the "play to" app on windows phone to play video from your phone to your xbox (just make sure you are on wifi). If you can't do it from your phone and your surface there is something else going on and I have no idea what it is.