Para aclararnos un poquito más y facilitarle la vida a los que te vamos a ayudar encierra tus códigos con la etiqueta GeSHi para ayudar a su correcta lectura así:

void insertaEnLista(list<list<Peticion> > lista, Peticion p)
{
    // CASO DE QUE LA LISTA ESTE TOTALMENTE VACIA, PARA EL PRIMER DATO QUE ENTRE
    if (lista.empty())
    {
        cout << "La lista enlazada grande estaba vacia asi que le aniado la 1º" << endl;
        list<Peticion> l; //CREO UNA LISTA DE LAS QUE CUELGAN
        l.push_back(p); //l.push_front(p) LE METO LA PETICION
        lista.push_back(l); // A LA LISTA ENLAZADA GRANDE LE ANIADO UNA PEQUENIA
        cout << "Se ha introducido correctamente la peticion de codigo " << lista.begin()->begin()->getCodigo() << endl;
    }
    else
        cout << "Aqui no entro porque la lista no esta vacia" << endl;
 
 
    if (lista.empty())
        cout << "Comprobacion: esta vacia" << endl;
    else
        cout << "Comprobacion: no esta vacia" << endl;
}

El problema echandole un vistazo al código es que  estás pasando una lista por valor, esto hace que se copie toda la lista de una variable a otra y modificas ésta última, no la original, por tanto tu cambio no causa efecto en la original. Efectivamente es eso, te pongo como dirían los ingleses un "minimal working example" con enteros para que lo modifiques conforme a tus necesidades:

#include <iostream>
#include <list>
 
using namespace std;
 
void insertaEnLista(list<list<int>> *lista, int p)
{
    // Si la lista está vacía de listas añado una lista nueva e inserto el elemento.
    if (lista->empty())
    {
        list<int> listaTmp;
        listaTmp.push_back(p);
        lista->push_back(listaTmp);
    }
    // Si no está vacía añade p a la última lista.
    else
        (*--lista->end()).push_back(p);
}
int main(int argc, char** argv)
{
    list<list<int>> miLista = {{3,4},{2,3}};
 
    insertaEnLista(&miLista,7);
 
    for(list<list<int>>::iterator it = miLista.begin(); it != miLista.end(); ++it)
        for(list <int>::iterator sit = (*it).begin(); sit != (*it).end(); ++sit)
            cout << ' ' << *sit;
}

Con la intención de poner más claro el programa he añadido un par de typedefs que acortan mucho los tipos que se suelen usar con las plantillas de C++:

#include <iostream>
#include <list>
 
using namespace std;
 
typedef list<list<int>> iDList;
typedef list<int> iList;
 
void insertaEnLista(iDList *lista, int p)
{
    // Si la lista está vacía de listas añado una lista nueva e inserto el elemento.
    if (lista->empty())
    {
        iList listaTmp;
        listaTmp.push_back(p);
        lista->push_back(listaTmp);
    }
    // Si no está vacía añade p a la última lista.
    else
        (*--lista->end()).push_back(p);
 
}
int main(int argc, char** argv)
{
    iDList miLista = {{3,4},{2,3}};
 
    insertaEnLista(&miLista,7);
    for(iDList::iterator it = miLista.begin(); it != miLista.end(); ++it)
        for(iList::iterator sit = (*it).begin(); sit != (*it).end(); ++sit)
            cout << ' ' << *sit;
}

Yendo al grano, tu problema es que tienes que pasar la lista por referencia para poder modificar la lista original y no una copia de ésta, asumo que si has llegado a listas te manejas con punteros, así que no debería haber problemas.

Un saludo.

Avesudra.