The gens Sempronia was plebeian, not patrician. The gens was promoted by Augustus to patrician status as part of his program to replenish the ranks of the patrician order after the deprivations of the civil war. There's a tradition found in Dionysius that the Sempronii were originally patricians, but like most such traditions it's usually considered a late addition, to justify the promotion of the gens to patrician rank. A similar tradition, for example, appears with the gens Junia and is unquestionably false. Their father Ti. Gracchus was likewise a plebeian, having held the tribunate in 184. Since ancestry descended through the male line the patrician status of Cornelia wouldn't have mattered.

The distinction between plebeians and patricians is an old one, and one that was increasingly irrelevant throughout the late Republic period. Originally, patricians were those families who could trace their male-line heritage back to the nobility, or senatorial class supposedly appointed by Romulus. The privileged patricians had exclusive rights to political positions and most avenues to power. However, following the Conflict of Orders, this distinction was much less important. The patricians found their numbers waning due to economic competition from plebeian families and intermarriage. Patrician numbers at this time could be bolstered only by careful marriage and fertility or, more rarely, by the adoption of foreign nobles into the Roman citizenship system (Broughton, Magistrates of the Roman Republic).

Eventually, the chief differences between patrician and plebeian were the limitations on certain offices: only patricians could hold a handful of priesthoods and only plebeians could hold the relevant Tribune position. However, the distinction was not completely meaningless. In the Republic period, as the leadership of Rome was polarised into the conservative optimates faction and progressive populares faction reacting to the Gracchi, there was some lining up of these factions along plebeian/patrician lines. However, many prominent optimates were plebeians so it is more likely that these factions corresponded to economic roles that correlated largely with the patrician/plebeian divide (Brunt, Social Conflicts in the Roman Republic).

As for the particulars of the Gracchi, they were indeed descended from Scipio Africanus, from the patrician Scipio stirpes of gens Cornelia. However, he was their maternal grandfather. Along the paternal line, the Gracchi were of gens Sempronia. Here it is complicated by the fact that gens Sempronia had both plebeian and patrician branches. The Gracchi descended from a plebeian branch, but there is some evidence that the Atratini branch were patricians. Some gens had both plebeian and patricians branches which could occur in cases of adoption, manumission, or when families had identical or similar names and were intermingled or confused over time (Oxford Classical Dictionary).