Parece que você está tentando usar uma string de conexão padrão do .NET. Você pode obter strings de conexão específicas do Azure aqui .
Acho que o problema que você está tendo é que você não especificou o provedor para usar na sua string. Se você estiver usando OLE você precisa dizer isso, caso contrário, você precisa referenciar os drivers SQL padrão do .NET. Você precisa ser muito específico com a string de conexão no Azure.
Veja um exemplo:
Provider=SQLNCLI11;Password=myPassword;User ID=[username]@[servername];Initial Catalog=databasename;Data Source=tcp:[servername].database.windows.net;
EDIT: Neste caso, a solução foi mencionada nos comentários - o SQL Browser Service não estava sendo executado e, portanto, não foi possível localizar a instância nomeada.