To or With
I am sure you must have spoken to the customer central before you were connected to\with me.
PS: Is there a better way to say this.
Either "to" or "with" would be correct, though I would probably use "to." Leandro-Z's suggestion is also grammatically correct, but it has a different meaning. Based on your statement, I would assume this call was transferred to you (perhaps by someone in customer central); based on his statement, I would assume the person called you directly.
Also, the use of "I'm sure you..." and "must" is a little redundant, though again, not grammatically incorrect. I would pare it down to "I'm sure you've spoken to/with..." or "You must have spoken to/with..."