The problem was not with the phone or APN. KitKat has a default setting of no dial up networking (DUN). I enabled it using the first method listed on this page. There are probably apps for this as well but the ones I saw required an in-app purchase to remove all restrictions.
Best answer by Yannick