Addressing women as "小姐" in Northern China I heard that it is not appropriate to call women or girls "小姐" in northern China. That it is considered rough and has a meaning close to "hooker".

So I never address girls or women as "小姐" in the north and even when I am in Shanghai or even further south. 

But is it really an issue? And if it is, what should I use instead? 
Right now I always use 姐 or 大姐 just to be sure I don't "hurt" someone.
Yes. It is an issue. But 姐 or 大姐 is not very appropriate sometimes. 


You can use 姐 or 大姐 to call a lady who is elder than you. But they'd better be not very young.
To call a young lady, 美女 is popular now in cities, though maybe they are not really very beautiful.
If there is some context, like to call a waitress, just use 服务员 or other address expressing their jobs. 
And at last, 女士, literal translation of lady, is always a choice.


Edited: It is an issue not because the meaning is used by everyone. But there are too many use cases, nobody wants to be misunderstood. Ironic, this is something like Gresham's Law.