Try contacting the Nagoya International Center. They offer job-finding services for foreigners in Nagoya, and there might even be job positions at the Center itself.
Nagoya International Center - The NIC - English Site
Hope you enjoy Nagoya - it's a great city.