I would be tempted to review what is in your startup (use Msconfig and look at startup tab, or download winpatrol). Anything that you don't recognise in there, or that might contact internet?
Also, I would've thought AVG would alert you if anything new tries to access the net? If so you would've had to approve it doing this?
Maybe the dial-up connection is the step before AVG kicks in but would've thought AVG would've caught it first.