fai questa prova:

1) crea un file (chiamalo come vuoi) con estensione ".udl"
2) doppio click sul file ".udl"
3) ti si aprira' una form in cui dovrai selezionare il provider, inserire username, password e Datasource.

se ti torna lo stesso errore di VB vuol dire che oracle e' installato male (alcune volte fa casino facendo l'aggiornamento dalla ver 7 all 8) e lo devi reinstallere

Anche io ho avuto il tuo stesso problema, da sqlplus mi collegavo, ma da VB no.