I'm afraid the advice you've been given is correct. EU hiring laws dictate that employers can only hire a non-EU citizen where there were no suitably-qualified EU candidates who could do the job. As you can imagine, this is not a very likely proposition.
If you're interested in working in Western Europe for an entire academic year (as opposed to just for a summer), there are one or two programmes that will enable you to do that. For more information on those, and on teaching in Europe, have a look at the advice guide I recently wrote: http://thirtysomethingteachertraveller. ... urope.html
Hope that helps.