There are as many different 'versions' of this song floating around as there are people who have played it. Jazz is like that. More specifically here, I don't think Justin has the latest version of the Real Book - I know he didn't when he wrote the list of 'recommended' books somewhere on this site.
Different editions of the book have slightly different chords for different songs, based on either who's version of the song they were using for their transcription, or if they got the original form from the composer. The newest (6th) edition is most likely to be closest to what the original composer wrote down.
In my Real Book the last two lines for Autumn Leaves run:
||F#-7b5|B7b9|E-7 A7| D-7 G7|
| F#-7b5|B7b9|E-| |
So in this case at least, Justin's chords match the newest Real Book edition.
As for Cmaj7 not being a hard chord - remember, none of these should be played with open chords [meaning chords with open strings in them, not 'open' in the music theory sense] if you want a 'tight' jazz sound. Use barre chords or 'four finger' chords (more often) so you can get nice 'crisp' changes.
Edit: Btw, when are we going to get our 'Blue Bossa' thread?