tw,
Frame Relay is obsolete because of MPLS, not the Internet
.
It's a heck of a lot easier to have the carrier provision an MPLS VPN solution using packet tagging than it is to provision circuits. One requires a few entries in an admin console, the other is an administrative nightmare. Both give the same result.
However, many companies don't realize this yet.