I believe multiple instances of the evaluation edition should work. Do you have the SQL Server Browser running and (if you are trying to connect from a different machine) its port, and the port in use by the second instance, open in your firewall settings? This page has a good reference of how to configure multiple instances for access beyond the firewall.
To confirm that the problem is/isn't the eval edition, add a named instance of SQL Express (you can remove it immediately after this test) - if the SQL Express instance is not connectible either than the eval-ness of the other invisible instance it not the problem.