Calculating significance of difference between two binary values on one dataset Suppose my sample comprises 350 instances. Each instance has two independent binary (pos and neg) evaluations, A and B. If my alternative hypothesis is that A is more often positive than B, how would I express whether the difference is statistically significant?

To be more precise on the data: This question came to mind when looking at patient blood serum data. These are 350 blood samples positive against X. Each sample may or may not also be positive against A or B, whereas A and B are both more often positive if X is positive, but biologically are not dependent on one another.
So my initial thought was to look whether A is more often positive than B. In the example it was, A is positive in ~80% and B in ~20%. So I thought about assessing this difference for significance and this is where I got stuck. :)
 A: You are conducting a one-sided test of a difference of proportions.  Because all four outcomes--A, not A, B, not B--occur often (70 times or more in this case), the Normal approximation to the Binomial distribution will be just fine.  Let $a$ be the number of occurrences of A, $b$ the number of occurrences of B, and $n$ the total sample (about 350).  Under the null hypothesis $a = b$ the variance of a single observation is estimated with the combined data, $s^2 = (a+b)/(2n) \cdot (1 - (a+b)/(2n))$. The variances of A and B are estimated as $s^2/n$.  The test statistic therefore is
$$z = \frac{a/n - b/n}{\sqrt{s^2/n + s^2/n}}.$$
The p-value equals $1 - \Phi^{-1}(z)$ where $\Phi^{-1}$ is the percentage point function for the standard normal distribution.
For example, with $n = 350$, $a = 280$, and $b = 70$, we estimate $a$ as 0.8, $b$ as 0.2, and $s^2$ as 0.25, giving $z = 15.87$.  Obviously that's not due to chance.  The result will be equally strong and obvious for any values of $a$, $b$, and $n$ anywhere close to these.
A: Your addendum suggests that A and B are dependent samples since they come from the same "instance", i.e., patient. In that case, I propose the McNemar-Test which tests for a (two-sided) hypothesis of unequal proportions:
> N    <- 350
> A    <- factor(rbinom(N, size=1, p=0.6), labels=c("pos", "neg"))
> B    <- factor(rbinom(N, size=1, p=0.4), labels=c("pos", "neg"))
> cTab <- table(A, B)
> mcnemar.test(cTab, correct=FALSE)   # no continuity correction
        McNemar's Chi-squared test
data:  cTab 
McNemar's chi-squared = 29.1236, df = 1, p-value = 6.79e-08

# alternative - Monte-Carlo permutation test
> library(coin)          # for symmetry_test()
> symmetry_test(cTab, teststat="quad", distribution=approximate(B=9999))
        Approximative General Independence Test
data:  response by groups (A, B) 
         stratified by block 
chi-squared = 29.1236, p-value < 2.2e-16

