It would have been very helpful if you have provided us with more extensive context, so we don’t have to guess and make unfounded assumptions about how you are going to use this term. Here are a few points to consider:
New country: I assume that by “new” you mean either “recently established” or “recently adopted” (as would happen when someone acquires citizenship in a country other than his country of birth).
If that is the case, then JADEED is the correct term for “new.” JADEEDA is the feminine form (in Arabic, adjectives take the gender of the noun it modifies).
If you specifically mean “newly established,” then NASHI’ (“burgeoning”) may be appropriate. The plural is NASHI’A (more on gender below).
What about “country”? The common term is BALAD (pronounced “BELED”), but you need to be extra cautious when you use it for the following reasons:
1. In classical Arabic, BALAD has been used for a variety of meanings, including “city” or “town,” as in:
"وهذا البلد الأمين."
Sura XCV, “The Fig”. (I hope you are able to display Arabic text on your computer).
Today, it is mostly used for “country.” This semantical shift has also affected the terms QARYA and MADINA, but that is a separate topic.
2. In the Qur’anic verse that I cited, the term is used as a masculine noun, but don’t be surprised if you see it used as a feminine noun (as in the answers provided by my colleagues above). This double-gender quality affects many Arabic nouns.
3. A variant of this noun is BILAD, which is always feminine, but BILAD is also used as plural of BALAD. When BILAD is used as a singular noun, its plural is BULDAN. (have I confused you enough?)
So, based on these considerations, your phrase, “our new country” would become:
BALADUNA ALJADEED (masculine)
BALADUNA ALJADEEDA (feminine)
BILADUNA ALJADEEDA (feminine)
The phrase above assumes a nominative case. Since I don’t know your full sentence, I can’t be certain of the case inflection. It may be BALADUNA, BALADANA, or BALADINA. I have left ALJADEED and ALJADEEDA without case inflection so as not to confuse you more than I have.
There are other terms for “country,” the usage of which is context-dependent. The term MISR (plural: AMSAR) was commonly used in the middle ages in reference to parts of the Islamic empire that lie beyond the Arabian Peninsula.
The term QUTR became very popular in the fifties and sixties when pan-Arabism wise a viable political movement. The idea was that the Arab world was one “country” (BALAD), but that each political division was a politically constituted unit. The term QUTR seemed convenient for that purpose. The Ba’thists of Syria and Iraq were most instrumental in popularizing this term, whichwas then adopted by the Nasserists. It is still commonly used.
The term WATAN is used today to mean “homeland” or “home country.” It used to mean “home” or “house,” as in:
ولي وطن آليت أن لا أبيعه، وأن لا أرى غيري له الدهر مالكا
I know this is a lot to digest, but that is what happens when you post a question with almost no context provided. In any case, I hope that the answers you received from everybody have helped.