You dind't say what the client OS was, only the server side, so it's hard to give very specific instructions. Some of what I'm suggesting may not make sense.
If you are using a fully-qualified domain name to access the share, then it is going to show as Internet by default - the DNS-to-zone determination is quite simplistic. When it sees periods in the name, it decides "Internet zone". For example, if you access \fileserver.domain.com, even from a machine in domain.com, the system marks it as Internet zone.
This can happen with DFS as well - for example, using domain-based DFS to get to send file shares to the client. In that case, the client is using \domain.com as the start of the UNC path for the share, and that will trigger the Internet zone.
To check this, use joeqwerty's suggestion of looking in the status bar. You may need to enable it on the View menu as later Windows versions don't enable it by default.
You can however change this through the IE settings in Group Policy:
If you are using only a host name such as \fileserver then that should map to Local Intranet. However, be aware that as of IE8 "Local Intranet" doesn't really mean what it used to - for instance see:
So you may be hitting on that here as well.
I understand you are asking about network drives and Windows Explorer but the underlying security settings for zones are the same settings.
I am somewhat simplifying as there are other possible things going on, and I'm leaving out some of the very low level details, but hopefully this is enough to point you in the right direction.
I should also add that you can mark all UNC paths as Local Intranet although that is dangerous - I would not recommend that even though it would be an easy fix in the "full name" scenario.