I was wrong. After rebooting, gnome-terminal was still under system_u:system_r:initrc_t context.
The fix was, edit /etc/selinux/[selinux config]/contexts/default_contexts. Copy the line for system_r:sshd_t and change it by sshd_t by init_t. pam_selinux can't find a correct context because there is no context available, coming from from init_t to the new user.
