It's the third that shifts, not the root - C to C#. The first two notes Brad sings on "we swim" are an E and a C#. C major wouldn't make any sense there.