If we move through time, then what is movement? That is to say how is movement, or any change for that matter, possible outside of the context of time?

One answer to your question is that there may be multiple "orders of time" and, in particular, there may exist an order of time that is separate from the one we normally experience and within which events can occur. Thus, for example, in Western Europe around and in the centuries before 1500 certain religious rituals, ecstatic experiences, moments in liturgical calendars, may have been experienced as occurring in a special "sacred time" that constitutes a different temporal order from commonplace "secular time." In his A Secular Age (and a book I've mentioned before on this site),Charles Taylor argues that our ancestors in Western Europe possessed this bifurcated experience of two orders of time and he provides a rich account of why it is that almost everyone alive today in Western Europe and North America experiences secular time only.

I was once asked at a University PPE interview, Does time have a colour? I found it both extremely interesting and baffling. My opinion was that as time was not a physical property it could not have a colour yet I questioned myself countless times. What's your opinion - could time have a colour? K(17)

I suspect the point of this question was to see whether you could articulate the idea of a "category error," that is a statement that is syntactically correct but is nonsense because its predicate cannot meaningfully be attributed to its subject. If this is what the interviewer had in mind, your answer was essentially correct but could have been stronger if you had explained that this was one example of a more general problem. If your interview was at an Oxford college, you probably would have earned bonus points if you had referred to Gilbert Ryle's classic discussion of category errors.

Is it sensible to think that time is more fundamental than space, because one can just close one's eyes and relive memories, going back in time or prospectively go forward in time to predict something, without actually changing your position in space?

Our experience of objects (including ourselves) in space and time seems vital to our human existence, and I'm not sure what it would mean to say that either spatiality or temporality is more important than the other. Since thinking about events that may have happened in the past or events is not literally time travel, so spatiality seems to "beat" temporality with respect to ease of travel, which your question refers to. The difficulty of self-directed travel through time doesn't mean that temporality is unimportant, however.