I'd like to re-open this bug.  I'm reproducing it on Ubuntu Gnome 13.04 Raring  64 bit.
Totally reproducible but this is what you initially observe
VLC stops playing a DVD about an hour into the film with the error
Playback failure:
DVDRead could not read 0/4 blocks at 0x200b8b.

If you look in syslog you see that it is because the player (VLC in this case but actually ALL players do the same) has tried to read past the last block in the DVD
Nov  1 23:03:23 aspire kernel: [ 3255.571794] sr 5:0:0:0: [sr0]  
Nov  1 23:03:23 aspire kernel: [ 3255.571795] Sense Key : Not Ready [deferred] 
Nov  1 23:03:23 aspire kernel: [ 3255.571799] sr 5:0:0:0: [sr0]  
Nov  1 23:03:23 aspire kernel: [ 3255.571802] Add. Sense: Medium not present - tray open
Nov  1 23:03:23 aspire kernel: [ 3255.571805] sr 5:0:0:0: [sr0] CDB: 
Nov  1 23:03:23 aspire kernel: [ 3255.571806] Read(10): 28 00 00 00 01 08 00 00 01 00
Nov  1 23:03:23 aspire kernel: [ 3255.571815] end_request: I/O error, dev sr0, sector 1056
Nov  1 23:03:23 aspire kernel: [ 3255.572795] sr 5:0:0:0: [sr0] Unhandled error code
Nov  1 23:03:23 aspire kernel: [ 3255.572799] sr 5:0:0:0: [sr0]  
Nov  1 23:03:23 aspire kernel: [ 3255.572801] Result: hostbyte=DID_OK driverbyte=DRIVER_SENSE
Nov  1 23:03:23 aspire kernel: [ 3255.572803] sr 5:0:0:0: [sr0]  
Nov  1 23:03:23 aspire kernel: [ 3255.572805] Sense Key : Not Ready [deferred] 
Nov  1 23:03:23 aspire kernel: [ 3255.572809] sr 5:0:0:0: [sr0]  
Nov  1 23:03:23 aspire kernel: [ 3255.572811] Add. Sense: Medium not present - tray open
Nov  1 23:03:23 aspire kernel: [ 3255.572814] sr 5:0:0:0: [sr0] CDB: 
Nov  1 23:03:23 aspire kernel: [ 3255.572815] Read(10): 28 00 00 00 01 08 00 00 01 00
Nov  1 23:03:23 aspire kernel: [ 3255.572824] end_request: I/O error, dev sr0, sector 1056
Nov  1 23:03:38 aspire kernel: [ 3270.315777] VFS: busy inodes on changed media or resized disk sr0
Nov  1 23:04:02 aspire kernel: [ 3294.082271] attempt to access beyond end of device
Nov  1 23:04:02 aspire kernel: [ 3294.082276] sr0: rw=0, want=12617616, limit=8629440
Nov  1 23:04:02 aspire kernel: [ 3294.082280] attempt to access beyond end of device
Nov  1 23:04:02 aspire kernel: [ 3294.082281] sr0: rw=0, want=12617592, limit=8629440
Nov  1 23:04:02 aspire kernel: [ 3294.182922] attempt to access beyond end of device

REASON:
It appears to be because the DVD you are attempting to play has more data than the one you just ejected and for some reason the length has not been updated so the DVD player "falls off the end".

Here is how to reproduce it

1) Reboot Linux
2) Put in a DVD that is quite short.  Mine is called RORY"
3) Navigate to it with the file explorer.  The DVD is correctly labled RORY on the left.
4) If you press <control>+L you can see it has been mounted to /media/andrew/RORY
5) Press the eject button ON THE DVD PLAYER
6) Take out the DVD and put in another DVD.  Mine is called OCEANS_TWELVE
7) Close the DVD tray and navigate to it with file explorer.  The DVD is correctly labled OCEANS_TWELVE on the left.

BUT
8) If you press <control>+L you can see it IS STILL MOUNTED AT  /media/andrew/RORY
9) Try to play with ANY dvd player and skip to near the end of the DVD.  

If the DVD you have in is longer than the DVD you ejected it will crash

WORKAROUND
Repeat steps 1 to 9 above but in step 5 press the eject button in the file explorer.  The DVD gets properly unmounted and when you put in the new DVD the file label and mount point are the same.  When you play the DVD it works properly.

The reason people are reporting that rebooting works is because when you reboot, the DVD you are trying to play is the first DVD that Linux sees and it gets mounted properly

THIS HAS BEEN DRIVING ME MAD FOR MONTHS.  EVERY TIME WE WATCH A DVD IT STOPS AFTER PLAYING!!

Now I realise all I have to do is properly unmount it and remount it and everything is hunky dory.

So I think the only fix required is to make sure that DVDs get properly UNMOUNTED when you hard eject using the DVD player eject button.  Being a noob I have absolutely NO idea how to do that.

Fixes anyone?  Anyone find that my steps above DON'T work please make sure that the first DVD is shorter than the second one otherwise you won't experience the same behaviour.