Since the folks at the Apple store had to reinstall the operating system on your Mac, in effect you now have a "new" Mac.
That being the case, Time Machine is going to try to back up your entire Mac. That is why Time Machine is taking so long in "Preparing".
You can let Time Machine keep "Preparing" and wait and see if it will backup everything.
Hopefully, you have the Mac connected to the Time Capsule using a wired Ethernet connection, as this process will be 3-4 times faster on average with that type of connection.
Another way of saying the same thing is that if you have a wireless connection between the Mac and Time Capsule, things are going to take a very, very long time to complete. Depending on how long "Preparing" has been going on, you might want to cancel the backup and then establish a wired connection so the next try will go much faster.
If Time Machine eventually comes back with a message that indicates that the backup is too large and the backup cannot be completed, you will need to think about adding another Time Capsule, or adding another USB drive to the Time Capsule and starting the new backups there.
You also have the option of erasing the Time Capsule that you have and starting all over again with new backups. The advantage here is that there is no additional expense, but the downside is that you lose your old backups.