Unaware that this had been occurring for while, DBA manager walks into our cube area:

DBAMgr-Scott: "DBA-Kelly told me you still having problems connecting to the new staging servers?"
Dev-Carl: "Yea, still getting access denied. Same problem we've been having for a couple of weeks"
DBAMgr-Scott: "Damn it, I hate you. I got to have Kelly working with data warehouse project. I guess I've got to start working on fixing this problem."
Dev-Carl: "Ha ha..sorry. I've checked everything. Its definitely something on the sql server side."
DBAMgr-Scott: "I guess my day is shot. I've got to talk to the network admin, when I get back, lets put our heads together and figure this out."
<Scott leaves>
Me: "A permissions issue on staging? All my stuff is working fine and been working fine for a long while."
Dev-Carl: "Yea, there is nothing different about any of the other environments."
Me: "That doesn't sound right. What's the error?"
Dev-Carl: "Permissions"
Me: "No, the actual exception, never mind, I'll look it up in Splunk."
<in about 30 seconds, I find the actual exception, Win32Exception: Access is denied in OpenSqlFileStream, a little google-fu and .. >
Me: "Is the service using Windows authentication or SQL authentication?"
Dev-Carl: "SQL authentication."
Me: "Switch it to windows authentication"
<Dev-Carl changes authentication...service works like a charm>
Dev-Carl: "OMG, it worked! We've been working on this problem for almost two weeks and it only took you 30 seconds."
Me: "Now that it works, and the service had been working, what changed?"
Dev-Carl: "Oh..look at that, Dev-Jake changed the connection string two weeks ago. Weird. Thanks for your help."
<My brain is screaming "YOU NEVER THOUGHT TO LOOK FOR WHAT CHANGED!!!"
Me: "I'm happy I could help."