This compiles, after supplying my own packet_entry_t structure.

Code:
template<class TTileAddress_t>
class packet_storage
{
private:
    typedef packet_entry_t<TTileAddress_t>                pkt_entry_t;

    typedef typename std::map<unsigned int, pkt_entry_t>::iterator iterator_t;

    std::map<unsigned int, pkt_entry_t> pkts_map;

public:
    packet_storage();
    ~packet_storage();

// problem 1
    typename std::map<unsigned int, pkt_entry_t>::iterator it;

//problem 2
    typename std::map<unsigned int, pkt_entry_t>::iterator find(unsigned int a,
                                                                unsigned int b);
    typename std::map<unsigned int, pkt_entry_t>::iterator find(unsigned int);
}; // end class packet_storage
It mostly needed more 'typename' keywords.

BTW I see no hash map!