This does not seem to be a contradiction. Once you are in the right region of solution space training is expected to be faster and easier. Re-initialization could have a regularizing effect, explaining the better performance.