In Visual Studio 2010, on the 'Attach to Process' dialog, check the two check boxes at the bottom that say 'Show processes from all users' and 'Show processes in all sessions'.
On doing that I found that I had my process show up twice, one running as System and one running under my local Windows login. I am not sure why (any input on this would be great!), but I was able to attach to the not-grayed-out one that showed up and was also able to step through my code this way.
The second one was the servicename.vshost.exe process as Ozz pointed out in the comments.
If you still do not see it, make sure your service is still running. Sometimes you might have a failing service that started and automatically stopped and therefore doesn't show up in the attach to options.