Stalls occur based on a wing's angle of attack rather than the aircraft's airspeed. (In fact, one of the basic facts that all pilots learn in their initial training is that an airplane can stall at any airspeed). The A330 measures angle of attack using vanes mounted on the fuselage:

However, below 60 knots, these vanes become ineffective. During the AF447 accident, the stall warning only engaged intermittently because the computers detected that the airspeed readings from the blocked pitot tubes were invalid, and therefore silenced the stall warning system.
Furthermore, because of the lack of valid airspeed data, AF447 was no longer in normal law (and therefore had no automated angle-of-attack protection), a fact which the pilots may not have been aware of. By the time the deicing equipment had cleared the pitot tubes, the aircraft was at such an extreme pitch that airspeed indications were still considered invalid, and the stall warning system did not activate. The computers only activated the stall warning system when the crew pitched down, which brought valid airspeed data back into the cockpit.
An Airbus press release suggests that this may have contributed to the accident:
We also note that the aircraft, or more specifically the design of the stalling warning system, misled the pilots: each time they reacted appropriately, the alarm triggered inside the cockpit, as though they were reacting wrongly. Conversely, each time the pilots pitched up the plane, the alarm shut off, preventing a proper diagnosis of the situation.
(Emphasis mine)