Is the data in your feature class from a version 9.3.1 SDE geodatabase? There was a known issue creating a 10.1 feature service against 9.3.1 data that may have produced a similar error message to what you are seeing. This was fixed in 10.1 SP1.
I am at Service Pack 1 and the data is from a 10.1 SDE geodatabase, but I am seeing this same error message. All of the datasets (in my case 4) are from the same SQL Server and same database. A truly perplexing error, at least in terms of the error message generated.
One thing to note is that this service features a standalone table and a join, but I have published other services with both of these special attributes without issue.
You might try exporting the data you want to use in your feature service to a fgdb and then importing it back to your SDE gdb (perhaps in a new feature class or table). I'm not sure exactly what ArcGIS Server uses to analyze the data prior to allowing you to enable feature access but I have seen instances where this procedure "cleans" the data so it is not viewed as being from mixed data stores.
I received the Cannot have "mixed" data stores with a feature or geocode service message today when I tried to publish a 10.2.2 feature service with data updates enabled. My map document only has one layer and that layer's data source is an ArcSDE Enterprise Geodatabase. I found that the issue was an image element that was added to the layout to display a logo on printed maps. ArcMap must package up the image and upload it to the server just as it would any layer source data that is not registered with the server. Once I deleted the image element from the layout I was able to publish my feature service.
Jay, thanks for posting this comment. I just experienced the same error today, running 10.2.2. I never would have guessed to delete the image elements in the layout window, but after I did this, it published successfully!
