Is this over-fitting or something else?
You've followed the right process well. (Well it's possible there's an error, like not randomly sampling the test set.)

I think the issue is simply that you have nevertheless overfit. The Kaggle held-out test set may not be, due to chance, that like the provided training data.  There's not a lot you can do except favor low-variance models more than low-bias models in your selection process.