The problem is that you are supplying the USB plug with the batteries, which give about 4.5V total (the panel is biased at the same voltage). Since the fan is a simple load, it'll just spin at the speed it can go (be careful with the current!).
The cellphone is more picky about the charging voltage, and depending on the model this can be more or less strict. You should check the specs for the phone charger, and eventually build a step-up to match the requirements.
Update
The voltage rating of the panel is indicative, and it will be satisfied only on determinate lighting (above a minimum level) and load (open circuit or very low current) conditions. Who determines the voltage is the battery pack, and in this case it's 4.5V. Then, the panel will give a current which is defined by a curve like the one below.

You can for sure use a 4 batteries pack, but then your panel won't be biased near the Max Power Point (MPP), which usually is around 70-80% of the maximum voltage (in this case around 4.5 V).
So you can use one more battery and then lower the voltage to 5V, but you'll receive less power from the panel; or you can use 3 batteries and step up.