Hola:
Puedes describir mejor que problemas tienes?
El error de conexión, ¿es cuando intentas acceder a la STK500 o es cuando intentas acceder al micro? ¿Puedes poner una screenshot del problema?
Si el fallo es de conexión con el micro, depende del micro, si los fuses se programan mal, igual no queda más remedio que usar el HVPP, o sea, la programación paralela de 'alta tensión' (creo que unos 15V o así). O quizás poner un cristal de cuarzo de 16MHz en el zócalo para tales efectos (no se si viene de serie), o incluso, según el estado en que estaban los fuses, 'inyectar' una señal cuadrada a la entrada de reloj. Depende de que problema haya con el micro.
Si el fallo es del STK500, hay que comprobar todas las alimentaciones y que el firmware del mismo esté correcto, cosa que sólo se puede hacer desde otro STK500, un AVRISP (unos 30€), o un JTAG, pero dudo que el problema sea este.
Si el fallo es que el micro está programado correctamente pero la comunicación serie del programa sólo funciona a veces, el problema puede ser de configuración del reloj, o simplemente que el oscilador interno no está calibrado.