If you can access the Internet, then it's not the mac address of the modem in the ASA.
When you change the modem, is the outside interface ip address of the ASA changed to?
Can you ping the ASA outside interface where you terminate the VPN?
If you run "debug crypto isa" and "debug crypto ipsec", where is the VPN failing?
I assume that you are trying to connect via IPSec VPN Client? Can you share the ASA config?