Hakhanoth for the weekday after Sseth HaKokhavim ("the appearance of three stars") on Mossa'ei Shabbath for the next day is not an issur of making preparations for the weekday on Shabbath, since it is no longer Shabbath but is the first day of the week. There is no such thing as "technically Shabbos" since it is either before or after Sseth HaKokhavim - which is itself the factor which determines which day it is, NOT the havdalah service. Thus, before sseth it is Shabbath wadhai ("Shabbos indeed"), and if it is after sseth then it is eino Shabbath ("not Shabbos").
However, it is assur le-khatehilah mi-de-rabbanan to do melakhah before one is mavdil either be-tefillath aravith or `al ha-kos (i.e. recites havdalah either in the evening prayer or over a cup).
So, to directly answer your question: Yes, there is a problem with doing melakhah (or presumably making hakhanoth for the following day) before one recites havdalah. It is not, however, a problem because of the issur of hakhanoth on Shabbath for a weekday since it is no longer Shabbath, but falls under the general rabbinic prohibition of resuming melakhah before the havdalah is recited.
However, if you have already recited ha-Mavdil ben qodhesh le-hol in your tefillath `aravith, then you are allowed to do melakhah, as long as you do not eat or drink (with the exception of water) until you also recite havdalah on a kos.
See - Mishneh Torah, Hilkhoth Shabbath 29:5-7; Arokh HaShulhan OH 299:19