Thank you both for your help and advice.
I was running my implementation in quiet mode (-q) as it gets a bit tedius after a while having to scroll through the bumf to then get the results. I hadn't even considered maximum iterations! I took the quiet mode off, and saw exactly what you said Keith, for C >= 100 it was giving a warning each time of "WARNING: reaching max number of iterations... optimization finished, #iter = 10000000", so this quite clearly explains why the results for Ein and Eout seemed random when the ordering of the data was changed. It was just struggling to converge with this data given this "harder" margin of C and this early termination caused the apparent randomness in results.
The annoying thing is, looking at this LIBSVM README file, I can see no way to output the "number of iterations" from the "model" which is returned from the svmtrain function. So may have to run everything NOT in quiet mode in future
Many thanks

Must say this homework has been the best yet, have learnt so much.