I have been told that is not safe to walk around the big park (next to the border) when it's dark because some friends had trouble for that.
Also when the sun goes down don't go in areas too far from the city center alone.
Any question, feel free to email me.
In the area leading from the town centre to the Gibraltar Border at night (the road where McDonalds is) there have been a few muggings on this road late at night (December 2006) mainly on Frontier workers entering or Leaving Gibraltar.
Is has been brought to the attention of the Major of La Linea and they are supposed to have increased Police Patrols in the area.
having said that, most of the area seems to be pretty safe elswhere, if in doubt get a Taxi, they are cheap.