Couldn't agree more. Though I don't find it all that painful - lots of editors/IDEs have a 'go to header file' shortcut that makes this take a couple seconds at worst.
But then I have repeatedly wondered why IDEs don't seem to have a way to synchronize your cpp changes to your header automatically. Rename function in .cpp -> automagically rename function in .h. That's all you really want a lot of the time.