I wrote Matěj šel tam včera and it was not accepted. Is the order of words important here?
Yes the word order is wrong.
Could you clarify why it's wrong?
The adverb "tam" behaves as a clitic (2nd position) in sentences where you do not emphasize it. If you want to emphasize "tam", place it first (Tam šel...)
Could you also place it last?
Yes, but not casually. You have to strongly stress that it was there and not here or overthere. Most likely when making a contrast "On šel sem, zatímco já šel tam.". or "Uděláme to tam." We will do it there (and not elsewhere).
What about 'Matěj včera tam šel' ? Also something a native Czech wouldn't say ?
The word order is wrong and it not sound naturally.