I've been using minis and a battlemat - drawn, then later printed (2d) or assembled (3d) - for a good 6-7 years now, and haven't had any real issues with it. We started with 3x, and then moved to Savage Worlds as the complexity of 3x wore on us. So note that most of my experience, and all of my recent experience, has been with SW.
That said, we use some of the same rules at the table. We mostly limit IC conversation, especially during tactical time, to a player's turn only, and this actually works pretty well. Once the players got used to it (and it was more a habit thing than a rules thing for my group), that part was pretty smooth. The card-based initiative system in Savage Worlds helps reinforce this, since the initiative shifts every turn and helps simulate the chaotic feel of a battlefield.
I haven't had much issue with my players and square counting or template finagling, but I like the additional rules around those, and will keep them in my back pocket in case that ever starts happening. In general, my players are way more about the general fun of getting together and playing, and less about optimizing characters or encounters (they are definitely not wargamers at the table). Heck, I don't even think all of the players have even read the Savage Worlds rules cover to cover, and they're a quick read.

Of course, that allows me to play fast and loose with the rules when it suits the mood or story, and from a DM's perspective, that isn't a bad thing.
I've found that the minis and terrain really do enhance the gaming experience. I know some might not like it, but for me and our group, its really helped speed up the game (not the reverse), and help us visualize things better. I've had a number of my players tell me how much they like using the minis and terrain. The only complaint I've heard from my group around the use of minis and terrain when when we first started and I used a lot of 3D terrain - the minis and fingers and such didn't fit very well inside the 3D walls. So I started using more 2D terrain with 3D props.
