Let me start by saying: go for it, f#ck the others and do it

The existing LUG won't be happy with you so expect "noise" (ignore it).
Go and advertise on local websites (news sites, free advertisement sites, etc.). Setup a (simple) website and mention the URL everywhere. The site helps people to find you and allows you to tell them when/where/etc.
Excuse the expression, but try to get into bed with big players such as Canonical, Linspire, etc. (the ones who have an ear for these kind of things). The very big ones (Novell, Red Hat, etc. won't be interested). The "smaller" ones are
Organise several meetings (several different days in a month) to allow people to come and visit (not everyone has the same days off).
Good luck!