To put all of this in one place:
a. The sample space is by definition all of the possible things that could happen. The collection of possible birthdays (blah, blah, no leap years, assuming that each birthday is equally likely) for three people is (Person A's birthday, Person B's birthday, Person C"s birthday). This is a Cartesian product, but ignore that for the moment. Each birthday may be represented by a number $1,\dots 365$ so the sample space of all possible birthdays is the collection of all possible triples $(a, b, c)$ with $1\le a, b, c \le 365$. Some possible birthdays, then, are $(19, 2, 350), (41, 41, 41), (200, 15, 200)$ and so on. Since the birthday for a person has no bearing on the birthday of another, the size of the sample space is $365\text{ (for person A) }\times 365\text{ (for person B) }\times 365\text{ (for person C) } = 365^3$.
b. The answer you were given comes from the observation that the number of ways all three people could have a birthday is to pick a date for person A (365 ways) and then use the same date for person B (one way) and for person C (again, one way), leading to the probability
$$
\frac{365\times1\times1}{365\times365\times365}=\frac{1}{365^2}
$$
The problem with your calculation is that you were counting one minus the probability that all three people had different birthdays. That's a perfectly reasonable event, but it ignores the other way three people could fail to have all their birthdays on the same day, since you didn't count the possibility that two had the same birthday and the remaining one didn't.