The pedestrians along Embankment in London are usually tourists so it's difficult to train them :-D I think the signage needs to be better - or I would rather the curb on the pedestrians was raised to make them think a bit.
The best bicycle lanes I've seen are painted in green with bicycle symbols here and there. I would think it's pretty universal. I don't know how costly this solution is though.