Alright, I think we may be onto something. If we check for the presence of value_type first, and then also for the existence of begin()/end() _and_ const_iterator, what else could go wrong?
Edit:I've tested a bit and it seems that with my SFINAE is_container trait everything works well, even in the presence of strings. This is great. Should we publish it somewhere? You should definitely post this on SO so I can give you an "accept". Perhaps we could send a copy to STL?