In short, the hadith is talking about the very first time both the Bait ul Muqadas (Temple of Jerusalem) and the Bait Ullah (Kaabah in Mecca) were constructed ... and this was before both Abraham and Solomon. Both mosques have been lost and rebuilt multiple times.
Regarding the Kaabah we have narrations in tradition that it was first built by Adam and possibly even before that by the angels. Similarly there are narrations that the Bait ul Muqadas was previously built by others and then rediscovered / rebuilt in the time of Solomon.
In the Torah there is mention of Melchizedek, a priest and ruler of Jerusalem in the time of Abraham who was on the true religion of Allah.
Note: Below are my own amateur, paraphrased translations and they may contain omissions and mistakes.
Ibn Hajar writes the following in Fath Al Bari:
قال ابن الجوزي : فيه إشكال ، لأن إبراهيم بنى الكعبة وسليمان بنى بيت
المقدس وبينهما أكثر من ألف سنة انتهى ، ومستنده في أن سليمان عليه
السلام هو الذي بنى المسجد الأقصى ما رواه النسائي من حديث عبد الله بن
عمرو بن العاص مرفوعا بإسناد صحيح " أن سليمان لما بنى بيت المقدس سأل
الله تعالى خلالا ثلاثا " الحديث ، وفي الطبراني من حديث رافع بن عميرة "
أن داود عليه السلام ابتدأ ببناء بيت المقدس ، ثم أوحى الله إليه : إني
لأقضي بناءه على يد سليمان " وفي الحديث قصة
Ibn Jawzi said: The problem with this is that Abraham built the
Kaabah, and Solomon built the Bait ul Muqadas,
and the time between them is more than a thousand years. It is
narrated by Nisai: "Solomon built the Bait ul Muqadas ... " And it is
narrated by Tibrani that: "David started the construction of Bait ul
Muqadas and then Allah revealed that it would be built by Solomon"
He writes in reply:
وجوابه أن الإشارة إلى أول البناء ووضع أساس المسجد وليس إبراهيم أول من
بنى الكعبة ولا سليمان أول من بنى بيت المقدس [ ص: 471 ] فقد روينا أن
أول من بنى الكعبة آدم ثم انتشر ولده في الأرض ، فجائز أن يكون بعضهم قد
وضع بيت المقدس ثم بنى إبراهيم الكعبة بنص القرآن ، وكذا قال القرطبي :
إن الحديث لا يدل على أن إبراهيم وسليمان لما بنيا المسجدين ابتدءا
وضعهما لهما ، بل ذلك تجديد لما كان أسسه غيرهما
The reply is is that this is talking about the first construction
and laying of the foundation of the masjids, and it is not Abraham who
first built the Kaaba, nor was it Solomon who first built the Bait ul
Muqadas. The Kaabah was first built by Adam and then his progney
spread through the earth. Hence it is valid that someone laid the
foundation of Bait ul Muqadas and then it was again built later. The
Quran associated the building of the Kaaba with Abraham, and it was
similarly said by Qurtubi that hadith doesn't provide evidence that
Abraham and Solomon were the first to build them, and their
foundations were laid by others.
He goes on to narrate various narrations about who could have been the first to build Bait ul Muqadas, and mentions traditions about the following:
وقال الخطابي : يشبه أن يكون المسجد الأقصى أول ما وضع بناءه بعض أولياء
الله قبل داود وسليمان ثم داود وسليمان فزادا فيه ووسعاه فأضيف إليهما
بناؤه
It is similar to Masjid Al Aqsa, which was first built by some Awliya
(guardians / friends / pious people) of Allah before David and
Solomon, and then David and Solomon expanded it.
And:
وقد رأيت لغيره أن أول من أسس المسجد الأقصى آدم عليه السلام وقيل :
الملائكة وقيل سام بن نوح عليه السلام وقيل يعقوب عليه السلام ، فعلى
الأولين يكون ما وقع ممن بعدهما تجديدا كما وقع في الكعبة ، وعلى
الأخيرين يكون الواقع من إبراهيم أو يعقوب أصلا وتأسيسا ومن داود تجديدا
لذلك وابتداء بناء فلم يكمل على يده حتى أكمله سليمان عليه السلام
The narrations about who built the Masjid Al Aqsa first. By Adam, and
it was said by the angels, ... by Shem son of Noah ... by Abraham ...
by Jacob ... the new construction was started by David and by Solomon
it was completed.
Another narration about Adam:
إن آدم هو الذي أسس كلا من المسجدين ، فذكر ابن هشام في " كتاب التيجان
" أن آدم لما بنى الكعبة أمره الله بالسير إلى بيت المقدس وأن يبنيه
فبناه ونسك فيه ، وبناء آدم للبيت مشهور
[Both the Masjids (Kaabah and Temple of Jerusalem) were built by Adam. He first built the Kaabah in Mecca, then went to Jerusalem and built the Masjid ul Aqsa ...]