do us a favour and take the upstairs light switch off and tell us what wires are in there.. my guess is that there is a red, yellow and blue... and nothing else...
you're missing a blue by the sounds of it too...
you'll have 2 twin reds, and 2 3Core and earth cables..
the 2 twin reds are 2 switch cables for the outside and hall light, and the 3 core with the blue cut out is the switch wire for the stairs light..
one red of each twin red goes to Com of 2 switches ( ie 1 red to 1 com, 1 red to other.. ), with the other red going to the L1 of the corresponding switch..
this sorts the outside and hall light, with the only problem being switch placement ( might not be on the "right" switch as before.. ), just swap them round if not "right"..
now the 2 3Core and earths.. the one with all 3 wires should go...
Red - L1
Yellow - L2
Blue - Com..
with the red and yellow from the other 3Core and Earth going to the terminals with the same coloured wire in them.. ( please check what wires go where on the upstairs switch and correct this order as needed ).
of course, without photo's or actually being there this is only a best guess, it's very hard to diagnose from words alone..