The problem I found was that Parity had skipped a nonce, so that the next nonce was actually "0xa", but Parity decided to put "0xb" into the transaction.
To resolve this I created another transaction specifically adding nonce of "0xa"
I can provide a high-level summary that will help things make more sense as you google around for the details.
They are separate concerns.
Validation is concerned with deciding if the transaction is allowed. For example, I can send a transaction that transfers all your ether to my account. Validators will notice that my transaction isn't signed with your signature, so it's not allowed by the protocol, therefore no state changes, and I loose all the gas I sent.
Other reasons to invalidate a transaction. Sender has insufficient funds, contract decided the input wasn't acceptable, contract decided the request wasn't acceptable.
Mining a block is a separate concern.
A block of transactions is a set of transactions in a specific order. Ordering is important because the network needs to determine an order for the transaction processing. Without consensus about the order of events, no consensus about the results is possible.
The challenge here is twofold. There is network latency, so nodes don't learn about pending transactions in exactly the same order. And, to be fully decentralized, the solution can't rely on anyone's clock because no one's clock is considered any better than anyone else's.
Miners order the pending transactions they know about and when they "find" a block they broadcast the solution to the network. This disambiguates the order of events so the network can reach a consensus about the order of events. PoW is like a lottery. The winner gets to "deem" that the transactions in the block unfolded in a certain order. They also get to decide which transactions (they may not know about them all, or the fees might be too low). Missed transactions will usually be processed in a subsequent block.
Confirming a Transaction
After the block with my (failed) transaction, there is a small possibility that a different miner will announce a block with a different solution. This will possibly contain the same transactions but in a different order, or possibly different opinion (byzantine fault tolerance) about validity. It means a block can be overturned by a better idea. Still, a new block arrives about every 15 seconds, so as these pile up the odds of older blocks being overturned becomes vanishing small. This is why it's customary to wait for a few confirmations for recognizing high-value transactions.
All together now:
My ridiculous transaction might be (say ...) the third transaction in a block with a result that I lost my gas. The network reaches consensus through the mining process that the transaction was the third processed by the network and the transaction was invalid and I lost my gas because of it. After a few more blocks arrive, we can be pretty confident we've seen the last word on the network consensus about my lame exploit.
Hope it helps.
Best Answer
It's basically impossible to guarantee a transaction occurs in a given block. There's too many factors--network latency, the block gas limit, uncles, miners who mine empty blocks, other transactions, etc. Chances are, by the time you're actually looking at block X, it's too late to get in block X+1, since a miner may have already decided what transactions to mine.
Technically, you could write a contract that only relays a transaction if the block number is right. This is unlikely to help you, as it will increase gas use in that transaction and therefore make it more difficult to actually get in that specific block.
It's also unlikely that you can get the first block after a crowdsale in general, because the specific block of the sale contract being created is also unknown. It's quite possible that, as a large contract, it won't fit and it will be delayed until the blocks aren't so full. The existence of the crowdsale contract could be checked by another contract, but again, this might not actually help you.
OK, but what do you actually do?
A higher gas won't help. It's how many steps, at most, the transaction will pay for. A higher gas price will give your transaction priority over others. The cost for a transaction is (gasUsed * gasPrice) wei, and one ETH is 10^18 wei. Note that no matter how much gas is specified, you only pay for how much you use.
Timing-wise, I'd just wait until the contract is ready, then send the transaction. There's not much use in trying to get it exact as soon as possible, since you probably can't.