I'm looking for a counter that can be incremented and will overflow with predictable behavior, preferably reset to 0 on overflow. I've tried using integers for counting but I'm getting weird overflow issues. Is there some library that provides an implementation of a counter?
Since you dont give the largest number your counter over flows at. You may want to look at libraries that implement arbitrary size integers. This means that there the integers can be bigger than usual - You would need to implement a counter, reset to 0 if the integer gets too big (just use a if statement if what youre doin is that simple-it sounds like it). So its entirely predictable for your purpose (whatever that is you didnt state). If you google around you will find libraries for arbitrary large integers for arduino e.g.
a library by Nick Gammon.