The only thing I could find in my notes is that John age 35, Olive age 33 and Benjamin age 10 lived in Tulls Creek district of Currituck Co, NC. in 1850. I have some books on NC but I am in the process of moving and they are packed away. If you keep in touch once I get settled I will see if I can find anything else for you. Also, they spelled their name Matthias and Mathias.
There were a lot of Matthias in the Norfolk and Princess Anne County area of Virginia. You might try there too. I have a John Mathias but he married Olive Flora. Too old to be your John.