Пройдохе графу пришлось незамедлительно «отправиться на охоту» за другой знатной и состоятельной невестой. И «объект» нашелся. Им оказалась восемнадцатилетняя красавица полячка Текла Валентинович, дочка обедневшего и малообразованного шляхтича из предместья Вильно. Пятидесятилетний Платон Зубов воспылал страстью к молоденькой польской красавице, в 1821 г. женился на ней, а через год отдал богу душу, оставив молодую жену богатой вдовой. Решив многочисленные юридические дела по наследованию огромного состояния покойного супруга, вдовушка отправилась «проветриться» в заграничное путешествие, во время которого она познакомилась с графом А.П. Шуваловым и в 1826 г. вышла за него замуж. Приехав в Петербург, молодожены вначале взяли в аренду пустовавший дом князя Михаила Александровича Голицына на набережной Мойки, 90, а через год купили этот прекрасный особняк.
Весь светский Петербург был покорен красотой и обаянием молодой полячки. По воспоминаниям той же А.О. Смирновой-Россет, «… все влюблялись в эту польскую волшебницу. Она научилась бойко болтать по-французски и была потом принята высшим аристократическим обществом; танцевала мазурочку пани так, что все старичье приходило в неистовый восторг». Дом графа А.П. Шувалова на Мойке становится одним из самых модных в Петербурге. В нем теперь регулярно собиралось высшее общество, устраивались блестящие балы и азартно играли в вист по 250 рублей за партию. Хорошо знавший графа Андрея Петровича камер-юнкер А.С. Пушкин любил бывать в гостеприимном доме своего приятеля, чтобы полюбоваться яркой красотой его жизнерадостной супруги или в азарте оставить за ломберным столом свой очередной авторский гонорар.
Обер-гофмаршал граф Андрей Петрович был весьма сметливым руководителем дворцовой службы. Он обладал редким даром в нужную минуту всегда оказываться под рукой, что чрезвычайно ценили хозяева Зимнего дворца – императоры. Граф А.П. Шувалов отличался пунктуальной добросовестностью, усердием и четкой исполнительностью, заслужив доверие и глубокое уважением императора и его супруги.
Александр I и его брат Николай I, зная о недовольстве своих придворных графом Шуваловым, о его всех раздражающей ловкости придворного, ставшей даже поводом к появлению обидного прозвища Пройдоха, справедливо считали все замечания в адрес графа абсолютно несправедливыми. Благодаря своей дотошности в придворной работе, точности в исполнении поручений, Андрей Петрович снискал к себе полное доверие императора и пользовался им до конца своих дней, получая высокие награды и чины.