Agreed. You need someone you can happily brainstorm with for hours and hours on end. If it isn't fun, if either of you would rather be doing something else, I find that's a good sign it's time to cut loose. Brainstorming problems is what you'll be doing endlessly when you are building a company together. I also find its the one thing most easily measured.

That being said, just because you can brainstorm with someone doesn't mean you'll be successful. You could be mediocre which is why it's easy for you to find someone you can brainstorm with. But it is a sign of a good cofounder.