В оказание данной услуги мне было отказано, со ссылкой на то, что данная генеральная доверенность не действительна, в ввиду того что в генеральной доверенности была указана моя девичья фамилия

Добрый день. Отказать в оказании услуги по предоставлению симкарты Мегафон мог при отсутствии возможности идентифицировать Вас, как доверенное лицо. Для оспаривания решения об отказе, необходимо получить письменный отказ. Оспорить Вы можете такой отказ в суде.

Согласно п. 1 ст. 185 ГК РФ доверенностью признается письменное уполномочие, выдаваемое одним лицом другому лицу для представительства перед третьими лицами. 
В соответствии с п. 1 Положения о паспорте гражданина Российской Федерации, утвержденного Постановлением Правительства РФ от 08.07.1997 N 828 удостовериться в личности граждан РФ позволяет паспорт. Следовательно, чтобы удостовериться в том, что указанное в доверенности лицо — это и есть предъявивший ее гражданин, необходимо сверить паспортные данные. 
При несовпадении паспортных данных доверенность нельзя однозначно считать действительной. Однако случаи  недействительности доверенности отражены в п. 1 ст. 188 ГК РФ. Приведенный перечень оснований является исчерпывающим.

Таким образом, если иных данных, отраженных в доверенности и совпадающих с паспортом, не имеется, тогда доверенность может быть не принята как подтверждение Ваших полномочий.

Здравствуйте, Оксана!

Вы правы. В статье 188 ГК РФ приведён исчерпывающий перечень оснований для прекращения доверенности.

Изменение фамилии к таким основаниям не относится.

Вправе ли они отказать мне в данной услуги и в какие органы мне стоит обратиться для решения данной проблемы?

 Сама по себе перемена фамилии подтверждается свидетельством о заключении брака, которое Вы представили сотруднику Мегафона.

Паспортные данные (даже если они и указаны в доверенности, причем данные прежнего паспорта) не являются признаками правоспособности личности гражданина. Такими признаками являются Фамилия, имя, отчество и место жительства гражданина.

Паспорт является только документом, идентифицирующим гражданина.

Но поскольку Вы представили сведения о своем прежнем паспорте, то оснований отказывать Вам в услуге у сотрудника Мегафона не имелось.

Что касается способов решения проблемы, то полагаю, что следует обратиться в офис Мегафона с требованием о предоставлении отказа в письменной форме.

Если будет отказано, снимите этот отказ на видеозапись, пригласите с собой свидетелей.

Далее сможете обратиться в суд с иском о защите прав потребителей.

Здравствуйте. 

В оказание данной услуги мне было отказано, со ссылкой на то, что данная генеральная доверенность не действительна

 Это, конечно, не так. Во-первых, по той причине, что основания для недействительности любой сделки (сделка в соответствии с законодательством — любое действие, направленное на появление, изменение или прекращение  прав и обязанностей) установлены законодательством: 

Сделка недействительна по основаниям, установленным законом, в силу признания ее таковой судом (оспоримая сделка) либо независимо от такого признания (ничтожная сделка).

И для доверенности такого основания для признания ее недействительной или незаключенной, как изменение фамилии (другого реквизита физического лица) нет. В то же время Вы верно указываете, что основания для прекращения доверенности указаны в статье 188 ГК. Однако обратите внимание, что эти основания касаются именно прекращения доверенности, это не отменяет того, что она может фактически перестать действовать и по иным причинам, например, в силу порчи или уничтожения ее как материального предмета. 

Далее, любая доверенность — это просто уполномочие одного лица другому и изменение фамилии, разумеется, не отменяет это уполномочие, поскольку такое изменение само по себе не меняет ключевые признаки правоотношения, связанного с доверенностью: воля сторон на то, чтобы передать свои полномочия другому лицу, их волеизъявление. 

Письменное уполномочие на совершение сделки представителем может быть представлено представляемым непосредственно соответствующему третьему лицу, которое вправе удостовериться в личности представляемого и сделать об этом отметку на документе, подтверждающем полномочия представителя.

Поэтому отказ незаконен, тем более если, как Вы указываете, в доверенности и паспорте совпадают все ключевые реквизиты, включая серию и номер паспорта. 

в какие органы мне стоит обратиться для решения данной проблемы?

 Во-первых, Вы можете попытаться связаться с начальством данного подразделения или главного офиса Мегафон, иногда это самый быстрый способ, одновременно можете направить письменную претензию (как почтой России, так и по адресу, если таковой указан на их сайте). Одновременно обратитесь с жалобой в Роспотребнадзор.