Not Associated With Trusted SQL Server Problem - Windows Service

I'm getting Not associated with a trusted SQL Server connection
errors on a .Net windows service I wrote, when it's running on my
application server.

It's not a problem with mixed mode security. I'm set for mixed mode and
I've been running the service on the app server for over a month with
no problem. My database is running on a second server and both are
under the same domain.

The problem has occurred twice over the last two months.

The windows service queries a table every 30 seconds, looking for
records to process. It's using a connection string and the user id is
setup and working in SQL. That when it's generating the error.

I've changed the connection string user id to sa and I still get the
problem. (server=xxx;database=yyy;user=sa;pwd=xyz)

The windows service is running under the domain/Administrator account.

I can run the windows service from a workstation with no problem. But
when I start it up on the application server, I get the 'not
associated' error back from Sql Server.

I'm trying to figure out where the problem is, and why it's
intermittent. Is it rights, policy, security? Why does it work for a
while then then error out?
Any suggestions or help is appreciated.

Thanks,
Eric