Hi,
Olimex recommends using the open-source avrdude program with AVR-ISP500. VisualGDB currently doesn’t support it out-of-the-box, so you would need to install and configure it manually. If you can confirm that the command-line programming with avrdude works, we can help you configure your VisualGDB project to run it automatically.
It could be also worth a try checking if the AVaRICE tool shipped with our AVR toolchain can recognize AVRISP MKII. If yes, you would not need to install any extra tools.