Visual Basic - RE:Problemas con instalador con Access

Lo más probable es que estés utilizando una ruta absoluta e.g. "c:\Documents and Settings\usuario\Documentos\algo.mdb" en las propiedades de la conexión. Si es eso, usa el objeto App para obtener información sobre la ruta donde se encuentra tu ejecutable (App.Path te devuelve esto) y establece dicha propiedad con CODIGO.

Si ese no fuera el problema, quizá debas intentar utilizar otro instalador que no sea el incorporado con Visual Studio porque este es nefasto. Prueba el Inno (www.innosetup.com), es GNU, muy bueno y muy parametrizable.

Respecto a Access, no es necesario que este instalado puesto que el propio sistema operativo ya contiene los controladores para esa BD. Si no, descargate la ultima versión del MDAC (Mocosoft Data Access Components) de la página de Mocosoft.