I think Coayuco might be overcomplicating things. Isn't this just the difference between a verb and a noun? When we say 'We need change', 'change' is a noun (we're basically saying 'We need (a) change'), but that won't work, because 'mudar' is a verb.. This is a guess, but I think it would be:
'We need change' = 'Nós precisamos de uma mudança' 'We need to change' = 'Nós precisame mudar'
Which, I suppose, is more logical than the English.