Preciso entender bem dessas coisas. Foi resolvido. Eu tenho uma solution com vários projetos, sendo um deles, um Web Service. Como no atual momento eu venho trabalhando no Web Service, ele está como meu projeto principal e tem seus componentes abertos no IDE, tais como o .svc e a interface. Sempre que crio uma nova conexão, me dá esse erro. O que fiz. Fechei o WS, abri o meu projeto principal mesmo, setei para o projeto de start up e qundo fui criar um novo edmx, funcionou como antes. Não sei porque mas era o WS.
Me precipitei. Voltou a dar o erro. Não tinha dado. Mas eu havia feito algo errado. Alterei e quando fui fazer outra vez, deu o erro já citado.
Descobri que o nome que ele monta é o nome da máquina onde está o banco. E não estava funcionando no IIS, devido a isso: Quando eu publiquei, tive que publicar o web.config devido a uma alteração que fiz(nunca mando o web.config, mas foi necessário desta vez). Só que para mim, o web.config estava apontando um ip onde está o banco. Só que esse IP é mascarado e é lido apenas de fora pra dentro. Logo, com o web.config tyendo esse IP ele não reconhece(de dentro), aí ele não acha o banco porque o IP não existe pra ele. Passei para localhost e aí funcionou. Agora sim, tudo resolvido.