The Random class simply uses pseudorandom number generation to give you a number that fits your specifications and seems random. Your code is fine, but with (in theory) 26 possible results, getting one of them shouldn't occur too often.
I believe the issue you're experiencing is that you're creating new Random objects in a loop, and they're ending up with the same seed, try declaring it in your class:
Random rnd = new Random();
And using it like so:
string randomString = a[rnd.Next(a.Length)];
The benefit of using this (as opposed to your current method) is that if you run it inside a loop you don't risk getting the same answer multiple times in a row.
Hope this helped, cheers!
~Winderps