Last time I had a wierd issue like this, I downloaded a new MDAC and loaded it on all my servers involved. Got their components up to the same level....

Well, like stated before, the Windows part of the servers communicated just fine, but SQL did not. You could ping, browse, map drives, all that stuff, just not connect to...