I suppose worse case I can get a prepaid card, as I'd lost my old one and had since upgraded to my bank's VISA debit branded card - but I'd really like it to be linked to my bank account this way.

I notice my bank says to enter the debit card number, and select VISA debit (or VISA if nothing) however the card updating form does not ask, but that might not be the issue - I enter it along with its expiry date and use the CVV2 or whatnot from the back of my card as my bank says to, but it comes up with the ominous "Your credit card was declined - contact your bank for details" with of course no details or record of failed transaction on my bank site, or anything.

Is this an issue with Linode? That it just doesn't know how to handle the debit number even though it's supposedly linked to VISA debit?

You need to call your bank and find out why THEY declined the charge.

Most times, it's a automatic decline, and they can over-ride it with your authorization for Linode.

_________________
Either provide enough details for people to help, or sit back and listen to the crickets chirp.
Security thru obscurity is a myth - and really really annoying.

I've been with a couple of Canadian banks during university, and some of them are ridiculously paranoid. (Are you with CIBC by any chance?) They'll decline a transaction and freeze your card at the slightest hint of unusual activity. Just call the number on the back of the card, ask to talk to a human, and tell them to stop blocking Linode. Unfortunately, depending on your bank, you may need to wait until Monday morning to do this, and any other transaction may be declined in the meantime.