arg, ya, mine always says fails too but then it connects after like 5-6 seconds after it gives the message it failed to connect. Don't ask me why this happens, I have no idea. : D
For your problem, hmm, well, you tried making a new connection and didn't work. Hmm, we need a techy in hear to help out.
What i've done in the past is reinstalled Mandy (I have done this a couple of times, i don't really have anything important) and tried it again.
Post something in the Hardware or Networking part of the forums, I bet their is someone that would be able to help you.