Превышение кол-ва дней пребывания (((
А в новом паспорте будет другая фамилия или имя и другая дата рождения? Если нет - то смысла в замене паспорт ноль. Иванов Петр, дата рождения 05.05.1978 + фото - вполне уникальные данные для идентификации. В украинские паспорта вписывают ИНН, там и фамилию поменять - не поможет.
Будут ли проблемы с шенгеном или нет - узнаете в следующий раз при подаче документов на визу. У меня знакомый получил немецкую визу для поездки в Германию, но поехал во Францию (прямым самолетом). И впустили, и выпустили без проблем. Но при следующем запросе визы - отказ. А у вас - нарушение дней пребывания, это посерьезнее будет. В базу ISIS эти данные заносятся обязательно и я очень удивляюсь, если там не стоит простейшая программа, которая ищет такие нарушения и ставит метку о нарушениях.