Learn Croatian: Činjenica da smo bili izgubili tu utakmicu velika je sramota. - The fact that we had lost that match is a big shame.

Yes! You could perfectly well say To što smo bili izgubili tu utakmicu velika je sramota. The phrase činjenica da (the fact that) is slightly more formal, while to što is very common in everyday speech. Both perfectly serve the function of turning the entire past action into the grammatical subject of the sentence.

Why is the verb smo bili izgubili used here instead of just the normal past tense smo izgubili?

This is the pluperfect (past perfect) tense, which translates to "had lost". It is formed by using the perfect tense of biti (smo bili) along with the past participle of the main verb (izgubili). You will see this used to emphasize that an action was completely finished further in the past, heavily separating that past event from the present state of it being a "big shame".

Why is the clitic je sandwiched between velika and sramota?

Because the subject is a long clause (Činjenica da... utakmicu), there is a natural pause in speech right after it. This pause creates a new breath group or intonation unit. The clitic je needs to sit in the second position of this new block of speech, so it lands right after its first word, velika.

What dictates the case for the phrase tu utakmicu?