That really confused me. Apparently you do not mean this song, as it’s just F Bb Gm C F Bb Gm C F F/Eb Bb/D Gm(b5)/Db F Bb F C :|| Bb(m) F. Though I must admit that I find that bass walkdown neat, especially since I’d never played it before, and yet figured it out live.
All I can find on YouTube with th song you are talking about are covers, many of them not very good. Any links to McCartney playing it? It looks like it would sound awesome.
Kashmir by Led Zeppelin popped in my mind first.
Not any of these: Four Chords
I learned most of the open chords on guitar by playing Lazy Flies by Beck. Chords.
I also really like the chords in Son of Sam and L.A. by Elliott Smith.
Lloyd Cole’s “Unhappy Song”
Chords
G xx5003 G5 3x0033
G/F# xx4003 D/F# 200232
G/E xx2003 Em 022000
G/D xx0003 D xx0232
C x32010 Am x02210
Csus2 x30010 A x02220
G G/F# G/E G/D C Csus2 C
la la la la la la la la la la la la
G G/F#
well, they were married in june
G/E G/D C Csus2 C
she was gone before the leaves were even turning
G G/F# G/E
she said "well, i knew he was a fool, but somehow i
G/D C Csus2 C
thought my welfare concerned him."
D G C
must the one always have to change
D G Em
whilst the other must always remain?
Am
must the cards all be dealt facing down?
A C D
turn away, turn away, turn your blue skies to grey.
G5 D/F#
now, when it comes to september
Em D C Csus2 C
i've got my own unhappy song,
G D/F# Em
october, november, december,
D C Csus2 C
and still she is gone,
G5
unhappy song.
Good call.
Time Warp has a fun progression.
The chorus of Stop in the Name of Love is supposedly A- G F G, but I’m not buying it. The second chord sounds way more like B- to me, making the change to F much more interesting.
“Edge of Seventeen” by Stevie Nicks. I’d also put this song into the “Songs with cool rhythms” thread, whenever someone starts it. It’s a great example of how to give a piece a strange but cool feel by emphasizing the off-beat.
I’ve always thought “That Was Yesterday” by Foreigner had great chords.
But, ya see, that’s different - **Kashmir **is just a funky tuning (guitar in DADGAD, not standard tuning).
Funky tunings don’t count.
(fwiw, there is the slimmest slice of truth to this, IMHO - there is a difference between cool chord changes and someone coming up with a funky tuning and just running their chording hand up and down the neck. Cool chord changes, again IMHO, are more than a neato tuning trick. Please also note that w/r/t Kashmir, Jimmy Page is NOT just “running his chording hand up and down the neck” - Kashmir is legitimately chock full of cool chord changes that also happen to be played in a funky tuning…that is all.)
Didn’t specify pop or rock, so I’m going with this one by Finnish folk band Varttina at 1.54. Yes, simple modulation, but it makes me want to go wooooooooooo! Time signature changes (not requested) also do it for me.
Tossing in again with “Blackbird” by Paul McCartney. I like playing this one on keys a la Billy Preston, although I can’t think of a hip way to play it on a solo job. I just play it for myself sometimes when I’m tired but still want to play. It’s odd the way the melody line colludes with the harmony. It’s a neat tune, IMO, and I’d have to think really hard to analyze it with Roman numerals. Just works, and you’ve got all the passing chords given their full due as melodically important.
Speaking of Billy Preston, “Nothing From Nothing” is simple, and it doesn’t work for me as a solo or small group thing, but the chords are hip and change nothing into something. “Holly Goes To California” same thing.
Thinking about Captain Beefheart in the “Critically Acclaimed but Unlistenable” thread reminded me of these two songs:
Her Eyes Are a Blue Million Miles
White Jam
I love the dissonance!
And I would guess this is par for the Beefheart course, but I’ve never been able to listen to any of his albums in their entirety. 
The Smiths had some interesting chord structures to their songs, and Johnny Marr of course was a great guitarist. I’ve always liked the chords in Some Girls Are Bigger Than Others (as repetitive as that song is) and Still Ill (do not be distracted by the spectacle that is Morrissey :p).
When I was in high school, I was a big fan of Alice in Chains and a good deal of that love was due to their unusual chord changes, but unfortunately I don’t have those albums anymore and don’t remember which songs are the best examples of this. I do like the key shifts in Would? (around 2:40).
I forgot about that! 
I last tried playing it in about 1984 or so, so I can be forgiven.
I remember that, even if you discount our band not having an orchestral string section, we never did get the sound quite right.
This one has some interesting transitions:
Ooo, Värttinä. A one-of-a-kind band. Good call. They did that song for an encore in concert. They taught the American audience to sing along on the chorus in Finnish! (It’s simple and easily picked up.) Most of the Americans in the audience were too shy to sing. I was in the front row, Susan Aho saw me singing, walked over, and held her mike up to me. Good times. Värttinä uses a lot of time signature changes in many of their compositions too (except not in “Seelinikoi,” which is an actual traditional folksong).
I’d like to match that with one of my favorite songs by them: “Mieleni Alenevi.” The OP asked for chord changes. Even though this is a drone-based song, it qualifies. It’s composed of 3-part (originally 4-part) vocal harmonies over a drone of throat-singing. The rapidly shifting chords using a lot of fourth, ninth, and eleventh intervals formed by the voices within a modal tonality over the drone are woven into a deliciously shimmering texture of delicately atmospheric harmonic complexity. This song always gives me shivers. It puts me in mind of Neolithic shamanesses chanting in hushed voices from 20,000 years ago. Since out of all the Uralic languages, Finnish is the one that most resembles Proto-Uralic, it can conjure up a hauntingly prehistoric atmosphere when handled like this. “Mieleni Alenevi” takes chord changes in an interesting direction because of how all the harmonies interact in complex ways with the drone, which is fairly unusual.
Too late for edit:
Another Värttinä song with cool chord changes is the very pretty “Aamu” (Morning). Especially on the chorus (Toi ilon illalle alun aamule…) where the chords sound like a conventional folk song, but done with such subtlety that you hardly notice that the chord changes are a bit unusual. The third verse also introduces more complex chord changes and shifting meters with such subtlety that they sound normal until you listen closely. It’s just magical.
I’m surprised that nobody in this crowd has mentioned the Grateful Dead yet. Aren’t they kind of known for their weird chord modulations?
Bumping this because a song on my ipod reminded me…
One band that consistently wrote songs with cool chord changes and melodies is Shudder to Think (band from DC active in the 1980s-1990s). Most of their songs have very strange meandering melodies and don’t follow verse-verse-chorus-verse patterns – instead, you can never tell what direction the song is going to go in from measure to measure. I don’t think they wrote a single traditionally structured song in their entire career.
Here’s the video for what was probably their “biggest” “hit”, Hit Liquor. If you want to hear more and you have iTunes, see if you can listen to a sample of the song “Kissi Penny” for an even better example (ignore the awkward cover on YouTube by some guy and his guitar).
Squeeze has some songs with awesome chord changes: