Learn Spanish (Latin America): Nosotros tenemos un problema grande aquí.

Yes, normally words ending in "-a" are feminine. However, problema is a rule-breaker! It actually comes from Greek, and many Spanish words of Greek origin that end in "-ma" (like el problema, el clima, el idioma) are masculine. That's why we use the masculine article un instead of una.

Why is it problema grande instead of grande problema?

In English, we put the describing word (adjective) before the noun ("big problem"). In Spanish, it's usually the other way around! The noun comes first, followed by the description. So, you say problema grande (literally "problem big").

Since problema is masculine, shouldn't the word for big be masculine too, like grando?

Adjectives in Spanish do have to match the gender of the noun, but words that end in "-e" are special. They are gender-neutral! So, grande stays exactly the same whether it describes a masculine word (like un problema grande) or a feminine word (like una casa grande).

Can I just say Tenemos un problema and leave out Nosotros?

Absolutely. Because the verb tenemos can only mean "we have", the word Nosotros (we) is optional. Spanish speakers often drop it unless they want to add special emphasis.