こんなんかな
db = MySQLdb.connect(host= DB_HOST, user = DB_USER, passwd = DB_PASS, db= DB_NAME, charset= "utf8")
db_cursor = db.cursor()
db_cursor.execute("SET NAMES utf8")

l_name_j_utf8 = l_name_j.decode("Shift_JIS").encode("UTF-8")
db_cursor.execute("INSERT INTO menu(name,id,name_j) VALUES (%s,%s,%s)", (l_name,l_id,l_name_j_utf8))