According to the error message, there is no MySql running on localhost. Make sure that you specify the right host and that MySql is up and running on that host!
I thought SQLyog and MySqlAdministrator use the same way (libmysql.dll) to connect to a MySql instance. If a personal firewall prevents SQLyog from connecting, then it should do the same to MySqlAdmin, shouldn't it! Unless a rule has been specified for MySqlAdmin…
No, do not remove ZoneAlarm, just configure it! If ZA detects a new program wanting to connect to the “Internet” (ZA says so, even if SQLyog wants to bind to localhost only), you'll be promted if access can be granted or no. You should check out the programs list as well in its control panel to see if SQLyog is included there or not.