After a lot of fuss, this is what I had to do (partial credit to: John Skelton):
Make sure you have added your name on the /usr/share/tomcat6/conf/tomcat-users.xml in the form (replace capitals):
<user username="USERNAME" password="PASSWORD" fullName="FULL NAME" roles="admin,manager,role1,tomcat" />
Then run:
sudo service tomcat6 stop
sudo apt-get install tomcat6-user
sudo chmod -R +rx /usr/share/tomcat6
tomcat6-instance-create ~/tomcat6
cd ~/tomcat6
rm -R bin
ln -s /usr/share/tomcat6/bin
ln -s /usr/share/tomcat6/lib
cd conf
ln -s /usr/share/tomcat6/conf/policy.d/03catalina.policy catalina.policy
Then point eclipse to your local instance and it should work (to verify check the project "Servers" created in your workspace and check that in the instance (i.e. localhost.config folder) you find a few files. Otherwise it didn't work.
You don't really need read and execute permissions on all the files in the tomcat6 folder, but it's a quick and dirty fix. You can always try to figure out which ones you really need. :)