I've just been dealing with this in my own game, transitioning from a simple roll-your-own tilemap system based around objects to a proper tilemap. Here's what I've found:
1. Using 'Is overlapping?' and 'On Collision' does not seem to be reliable for tilemaps when fast moving objects -- bullets -- are in play. If the bullet moves too far into a tilemap section without destroying the tile or itself, you can't get collision information. Example: Is overlapping will come up 'no'.
2. Ashley explained how tilemaps are automatically broken into square sub-sections when you have large areas full of the same kind of tiles. I assumed that you could still tell when an object is inside on of those squares, but apparently you can't. It's almost like the interiors of the sub-sections are simply tiled backgrounds. All you can reliably collide with are the borders.
What I did about it:
I just bypassed the 'on collision/is overlap' commands by rolling my own. I'm just testing each bullet once per tick and seeing if there is a tile at the same position. If there isn't, I move on to the next bullet; if there is I do further filtering by tile type to decide what to do (Tile A: bounce bullet, Tile B: destroy tile, Tile C: Destroy bullet & tile, etc...). This seems to be working perfectly.
Hope that helps,
P.S. The other thing I've done is switch from the built in bullet behavior to using the Custom Movement behavior. This has resulted in a MASSIVE speedup for my application. I can now put a couple thousand fast moving bullets onscreen with no slowdown and faultless tile collision. <img src="smileys/smiley4.gif" border="0" align="middle" />