I'm aware of measures like number of distinct cell types being used as a measurement of complexity in biology, for example in the G-value paradox. But this doesn't really help for unicellular organisms. Is it possible to define a unit of complexity to make comparisons between different organisms?
This is a very interesting question. Not sure if there is any way to answer without specifying a definition for complexity.
It is clear that everything is made of only the same few elements, so complexity must involve more than that. Do the number and position of identical molecules matter? If so, size matters and we would label a large jelly-fish as more complex than a cat and the air in a large hot-air ballon as more complex than any single living organism (assuming it is bigger).
I think it is clear that this is not what is meant by biological complexity. Molecules acting identically should not count multiple times; the number of different molecules matters more than the mere number of molecules. But are immune cells really more complex simply because of a relatively minor difference that allows them to generate a wide variety of genetic variants?
What about the variable coat color of a calico cat. Does the complex and non-repeatable (even with cloning) pattern mean it is complex, or does the fact that a simple genetic process underlies it mean it is simple.
The difference in complexity of different representation of the same thing is a classic problem in information theory (see Kolmogorov complexity). The ratio of the circumference of a circle to its diameter requires an infinite number of decimal digits to describe, but it is just a single geometric concept and it can be represented with one or two characters, as pi or π. This applies to the problem of using phenotypes to measure complexity -- the language and definitions we use to describe or to differentiate phenotypes determines what is complex and what is simple.
Moving beyond a simple static snapshot case, biological complexity involves time-dependent evolution. The "game of life" demonstrates how simple rules + initial conditions yield apparent complex behaviors, and the beauty of fractals arises the same way. Many apparently complex organisms grow from small seeds plus time-evolved exposure to simple things like water and light and CO2. Are trees only as complex as the seed they grow from?
Finally, what about higher order complexity? One human brain is very similar in general makeup to another, but the concepts and memories stored seem complex and very different. Comparing the complexity of stored information between two people is the whole complexity problem over again.
It seems to me that complexity can only be cleanly measured within a specific context, and then only relatively. One can measure the relative genomic complexity of two organism as the edit distance between the alphabetic sequences representing their genomes. The relative regulatory complexity can be measured as mentioned above by @user1682. Each of these says something about an organisms complexity. But what if organism A has higher genomic complexity and organism B has higher regulatory complexity? It might be possible to derive something like a principle component "basis set" from several of these kinds of measurements using a training set and a list of organisms with predefined complexity values. Applying this "standard" scoring metric to another organism would allow ranking it on a "standard" scale, but it would be difficult to generate and obtain consensus on the initial "expert" ranked organism scale. Such a standard might have some value, but is not really theoretically satisfying in that it describe an organisms complexity in the same way that the average of a small sample describes the distribution of a large population.
I don't know if it is helpful for your problem, but I measured complexity in gen regulatory networks by parsing them into boolean networks. Then you can initiate all nodes with a random boolean value and update the network until it reaches an attractor. For a hand full of initial states you can compute the average entropy and mutual information. Additionally the topology (scale free, small world [Barabasi]) and count of reached and cycle lengths as well as robustness (reaching same attractor by flipping a randomly chosen node in the trajectory) can give you information about the complexity. To compute all attractors by all possible initial states of the boolean network can be done with a sat solver [Dubrova].