Como está utilizando Python 2.7, debe especificar que su cadena contiene Unicode.
>>> db.session.add(Users(u'ä'))
También puede usar una importación futura para tratar todas las cadenas como unicode.
from __future__ import unicode_literals
Alternativamente, puede actualizar su versión de Python. 2.7 es la última versión que trata las cadenas como bytes en lugar de unicode.
Editar
También deberá actualizar su __repr__ para que maneje correctamente Unicode.
def __repr__(self):
return self.name.decode('utf-8')
o cualquier codificación que quieras usar.
En general, deberá asegurarse de manejar la codificación y decodificación a Unicode. No puedo urgirle lo suficiente como para que considere usar una versión más reciente de Python. Uno de los mayores cambios en Python 3 aborda este mismo problema.
