Pretty sure this is the Web Shield by how you describe it, so a far safer short term work-around would be to disable only the WebShield, not all of Avast.
This part leaves me with a question:
Until then I had to either wait approximately 5 - 10 minutes or restart my pc.
Is the problem intermittent (comes and goes), constant, only happens after startup and then goes away after a period of time? A reboot temporarily clears the problem?
Either way, one thing to check is to see if all instances of Avast! are allowed in your firewall settings. If it looks like nothing is being blocked, you could try deleting any Avast! related rules on your firewall, then let them be re-created.
As far as Java, I cant recall seeing any Java-related problems with Avast! posted here on the forums, could you provide a link to where you saw this if you have it available?
Whether or not any of that helps, post back and let us know if it did or did not work.