Connaître vs. Savoir

Yep. If you "connais" Paul Bocuse, it generally would mean you know him personally, not just heard of him. Like if you "connais" Paris, you would have been there, not just know that it is a city in France. Je ne connais pas bien Paris, mais je sais que c'est une ville de France. The verb "connaitre" is followed by a noun and can't be followed by "que" or "qui".

Yes, vraiment. ;)

The difference is sometimes hard to grasp for English speakers since the English language has only one verb of "knowing" something.

Connaître is about a personal, concrete knowledge of something or someone. Think about it as "recognize" without the "-re". What does "recognize" really mean in English? You have a concrete image of something in your head and then you match that concrete piece of knowledge to something you see. That's the kind of knowledge conveyed by connaître.

Je connais cette personne. -- I know this person. (In the sense of you recognize her.)
Je connais la date. -- I know the date. (You have the date stored in your memory and now you match it to what you just heard or saw.)
Je ne connais pas Vienne parce que je n'y suis jamais allé. -- I don't know Vienna because I've never been there. (Here, you're lacking a concrete piece of information.)

Savoir is more of an abstract kind of knowledge or even an ability one might have.

Je ne sais pas quoi faire. -- I don't know what to do.
Je sais nager. -- I know how to swim.

Here are two similar questions to highlight the difference:

Est-ce que vous savez quand il viendra? -- Do you know when he is going to come?
Est-ce que vous connaissez le date de son retour? -- Do you know the date of his return?

In a nutshell:

Savoir : to know a fact; or how to do something.

Connaître: everything else that's not strictly "fact/how to do something".

I respectfully strongly disagree with Chris in relation to the last part of his reply that seeks to highlight the difference.  Do  you know the date of his return concerns knowing a fact (the date) and "savoir" should be used.

I find it easier to associate "connaître" with "familiar" : Je connais Paul.  I know Paul (he is familiar to me).

Here is a (hopefully) useful example of the usage:

Je sais le nom de la rue, mais je ne connais pas la rue.

I know the name of the street [fact], but I don't know the street [am not familiar with it - this clearly does not fall into the "fact/how to do" category]

As to Paul Bocuse, a famous person (chef?).

Je connais Paul Bocuse [he is familiar to me / he is an acquaintance / I recognise  him].  Je sais qui est Paul Bocuse - un chef célèbre.

"Je sais qui est Paul Bocuse" is in essence an abbreviated way of saying that you know a fact about him - his fame, his occupation etc - rather than simply recognising him.  It only seems tricky because the statement has implicit content rather than being fully described.