First, your initial setup was correct. It is better to have the service interfaces defined in the web app, and have your Android app draw from there. I'm not sure what IDE you're using, but in Eclipse, the feature you want to use in the Build Path dialog is called Link Source. Using this, you can point a build path directly to the web app's service interfaces in a way that they will be compiled with (not against) the Android app.
As a brief reference, take a look at the Setup in Eclipse section of the Android wiki in the SyncProxy project: https://code.google.com/p/gwt-syncproxy/wiki/Android. Also check out the Common Issues wiki. https://code.google.com/p/gwt-syncproxy/wiki/CommonIssues
As a point to note, the way it ultimately functions is not that the web app exports the code to the Android project. It is actually that the Android project will import the code into it's own source hierarchy from the GWT app source path.
With regards to the second error you received, the "lost" policy file, try running a GWT compile on your project and make sure your appengine-web.xml file, if using GAE as your service backend, has been modified as defined in the wiki (I just made a few updates).
Lastly, you may run into a one more error. Since you are using GWT 2.5.1, you may hit a serialization issue if you aren't running with the most up-to-date version of the SPALibrary. I'm going through the feedback on the tests for that now, and should have that file available for download within a few hours on the site. Please make sure to use 0.4.1 Android library if running against a GWT 2.5.1 ServiceImpl.