Step 1: Square both equations:
\[
(a \cos \theta + b \sin \theta)^2 = 16
\]
\[
(a \sin \theta - b \cos \theta)^2 = 9
\]
Step 2: Add the two equations:
\[
a^2 \cos^2 \theta + 2ab \cos \theta \sin \theta + b^2 \sin^2 \theta + a^2 \sin^2 \theta - 2ab \cos \theta \sin \theta + b^2 \cos^2 \theta = 25
\]
Step 3: Simplifying:
\[
a^2 (\cos^2 \theta + \sin^2 \theta) + b^2 (\cos^2 \theta + \sin^2 \theta) = 25
\]
Since \( \cos^2 \theta + \sin^2 \theta = 1 \), we have:
\[
a^2 + b^2 = 25
\]
Thus, the correct answer is \( \boxed{25} \).