Wouldn't hurt to change the MAC of the router (and the SSID while they're at it).
They can change the router, and eventually the problem should sort itself out (if it is indeed their router and not a neighbor's that is the issue), but it's going to take until the old record ages out of the database for it to happen. And that could be months or years.