I know that if you are Australian then you just have to go to the Aussie consulate with your marriage certificate and fill in forms for a new passport for the name change (I believe it does not cost anything if done within the 1st year!). I believe it should be the same for which ever nationality you are, best thing to do is check with your consulate.
Not sure if its the same procedure, are you referring to a HK ID card + Passport name change? basically this is what I did.
Get a deed poll drafted by an Attorney,
go to the immigration center in Wanchai with the deedpoll and they'll do the rest/no appointment needed (for your HK ID card).
They will issue you a temp ID in the same day, take that downstairs to the Passport department with your old passport and they'll do the rest. I picked up my ID + Passport 3 weeks later if I remember right.
Same here.
Needed to change my passport first at the consulate (it took a while and was about HK$900) then went to Immigration with my new passport to change the ID card.
You definitely need to change your passport first though.