Alot of computer issues regarding the mobo are very difficult to nail down. The time in the "store" shop is mostly dependent on you and how willing you are to make hard decisions and how much effort they are putting into trying to find the real answer to your problem. This is an important note. If you don't work with them and be flexible then you could be going through a series of attempted solutions that cost you alot of money. They more they are willing to try to understand the issue, and the more flexible you are in deciding what to do, the faster you'll get your machine back. I deal with this all the time, believe me.
A couple things to keep in mind. There are a large number of potential issues you could possibly have with not just hardware but software. Often times when you go in and you don't give a good description of the issues you are having the longer it will take to find the solution, but moreover, the less willing you are to discuss, and thoroughly, what is happening and when it first occurred the less likely you'll get a prompt solution from them. If they have to follow inexperienced observations and find them to be dead ends the more likely it will be that they have to backtrack and seek out the actual issues on their own.
Most technicians, I'm sure, know that first you must resolve the hardware issues and then work on the software issues. Even so, some of the hardware issues are very hard to nail down and seem to be problems manifested in software. For instance, I have a compaq "uwave" mobo here that installs an OS fine, runs fine for about 8 hours, and then locks. One would think it is the OS the way it behaves but I guarantee you it is the hardware. I've replaced the cpu, memory, hdd, cables, power supply, video; everything. It still locks. The components have all beeen tested in other machines and work flawlessly, but anyone experiencing this problem could be working on a software solution for some time. It was very difficult for me to narrow down and I had to test alot of things over a long period of time.
Suffice it to say, the pearl of wisdom is patients. Most repair shops have machines coming in all the time.
As for your actual problem. An OS such as Win98 can be updated without doing an install. It will sense the new components and just load the drivers and related files. If you are using Win XP then you have a different story. You normally cannot just switch the mobo and have the OS update the drivers--M$ calls that progress I guess. Many times you can't even reinstall over the top without wiping out what you had before. So, no it isn't always safe.
But the guys in the store should have told you this. They probably have a fee for OS reinstall. If you chose not to have them install then the burden is on you to resolve all the problems relating to the OS and the new board.
You probably had to buy a new processor because your new board wouldn't take the processor you had. I've seen people hold onto their old PIII 600s and then their board goes out. They need a new one and have to replace the processor to boot. If you were able to maintain your old ram, then well, great.
The point is this. If the mobo goes out then they tell you that it is gone and that you will need a new mobo/processor they aren't acting rinky dink. If they offer you the service of installing the OS onto the system and you decline then you have to deal with the M$ deficiencies on your own. Sometimes it takes a while to narrow down the problem and a way to speed it up some is to be very descriptive of when it started and what it actually is doing and it behooves you to actually speak to the TECH that is working on the machine for you. Finally, because they have machines coming in all the time the difficult ones take longer as customers are dealt with and the faster easier problems are taken care of while they wait for your call back or you to make decisions on what action to take or to research the right replacement parts for you. And last but not least, the owner could be proficient in computers and incompetent to boot attempting to dictate solutions to the techs that do nothing but hinder their progress (seen it, see it every day).