The problem seems to be with Tomcat, not the server machine.
Test 1:
I changed the port (server.xml Connector port) to 96 and restarted Tomcat.
Result: No change; i.e. worked ok on local machine, could not access from others.
Test 2:
Stopped service on both Apache2 and Tomcat. Changed Tomcat's port to 88 (same as Apache's). (Note that Apache server has been working just fine for all machines on my LAN.
Restarted Tomcat but not Apache.
Result: Exactly the same.
Conclusion: The problem seems to be with Tomcat; most likely its setup.