I just got off the phone with ESRI tech support with a solution that worked on our system.
Apparently there was something wrong with our DNS service so that it wasn't passing along host names (I don't really understand this part) So there are two options: fix the DNS, which I don't as of yet know how to do, or instead of using the host name when referencing the database use the local machine IP (IPV4 not IPV6).
For example:
When I wanted to connect to the database
in the field "Instance:" I would use "server\GISsql" which gave the error.
The way that works is to use the machine IP "192.168.0.555\GISsql"
I am sure that is clear as mud, but if you have specific questions I can probably explain it better.
Here are the specs of my system so you can see if yours matches up and this solution would work for you.
ArcGIS 10.1
SQL 2008 R2 express
Windows 7 professional
Operating system authentication
Way excited that it works!