does the change take place between the slow, moody opening and the second part where it speeds up (4min 4sec about).

Yeah that's right, here it changes from harmonic minor to pentatonic.

Second, is there any way of working out scales that will sound right in the same key? eg as u said the solo uses D and E keys but still sounds right - is there any other than just trial and error? Hope u follow that...

Yeah I get ya, you want to know if there is a way of knowing which scales will sound good in a given key, as in the sweet child of mine example. I'm not a huge theory guy so I'm going to leave somewhere more adept in theory to answer that one. You can never go wrong with trial and error though.