Before I continue, I probably should mention that I already have tried copying vertex groups and mirroring there and also mirroring through the weight tools (I believe it's the same thing, but still), have X Mirror option enabled as well (yet it looks like it ignores it for some reason). The model is centered in the scene, everything looks fine, vertex groups names should be fine as well. No idea what's going on there, but whenever I try to copy one vertex group to another Blender hiccups and shows a error, that says: 0 vertices mirrored, 228354 failed.
Here's the file with the problematic mesh: https://drive.google.com/open?id=0B73O5HTSV-kHZ0hldVJ6RDdYMGM
So, as you can tell that last rigging part basically now has killed the whole work I did there. Thanks in advance, kind people, I really hope that some Blender veteran knows what's going on.