I have not come across this issue before but here is what I would try. On the client machine, can you create a connection to the cube using Excel? If so, that shows that connectivity works. Then, I would check to make sure you have the same version of OWC, OLE DB, ADOMD, SNAC, etc. Is this SQL 2005? If so, have you applied the latest updates (http://support.microsoft.com/kb/953752)? And have you applied those to both the client and server?
--Craig