I no-followed all my links because that seems to be in the spirit of what Google want. I think it's ok to have the footer links there because you built the site and if people like it you've let them know who built it and where to contact you. But it says nothing about the quality of your site in a 'natural' way, as you put it there, it wasn't done by a third party. I think it could be seen as manipulative.
Anyway it doesn't seem to have affected my ranking, well my ranking has improved slightly, but I have been doing other stuff too.
PS. I would be very wary of 'SEO Experts'. Google webmaster forums is full of sad stories about people who have hired them and their websites have disappeared from the rankings.
There we go, my first contribution (apart from saying hello).
Cheers
Mike