You shouldn't have to call header before calling redirect. In fact, redirect shouldn't work properly after calling header, because header prints an entire HTTP response header.

So it must be something else. Are you using the same URLs when you test redirect vs. Location? Be forewarned that using relative URLs often doesn't work properly. Could that explain the problem you're having?