Everyone is going to place different value in different parts of their marketing strategy, so only you can ultimately decide if its worth it or not.
That being said I would not pursue this service. They have a decent traffic ranking in Canada, but not enough to warrant what they're asking for, in my view. And with the nofollow and php redirects, you're getting no SEO benefit from the service, only whatever traffic they send directly from their site.
